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:
“... geometry became a symbol for human relations, except that it was better, because in geometry things never go bad. If certain things occur, if certain lines meet, an angle is born. You cannot fail. It’s not going to fail; it is eternal. I found in rules of mathematics a peace and a trust that I could not place in human beings. This sublimation was total and remained total. Thus, I’m able to avoid or manipulate or process pain.”
—Louise Bourgeois (b. 1911)