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:
“I am present at the sowing of the seed of the world. With a geometry of sunbeams, the soul lays the foundations of nature.”
—Ralph Waldo Emerson (1803–1882)