Computational Geometry
- Testing whether a tree may be represented as Euclidean minimum spanning tree
- Unit disk graph recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)
- Many motion planning among polygonal obstacles in the plane are NP-hard.
- Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from A\S by a collision-free rigid motion of S, and such that both S and A\S are connected.
- Art gallery problem and its variations.
Read more about this topic: List Of NP-complete Problems
Famous quotes containing the word geometry:
“The geometry of landscape and situation seems to create its own systems of time, the sense of a dynamic element which is cinematising the events of the canvas, translating a posture or ceremony into dynamic terms. The greatest movie of the 20th century is the Mona Lisa, just as the greatest novel is Gray’s Anatomy.”
—J.G. (James Graham)