List of combinatorial computational geometry topics

List of combinatorial computational geometry topics enumerates the topics of computational geometry that states problems in terms of geometric objects as discrete entities and hence the methods of their solution are mostly theories and algorithms of combinatorial character.

See List of numerical computational geometry topics for another flavor of computational geometry that deals with geometric objects as continuous entities and applies methods and algorithms of nature characteristic to numerical analysis.

Construction/representation[edit]

Extremal shapes[edit]

Minimum bounding box (Smallest enclosing box, Smallest bounding box)
- 2-D case: Smallest bounding rectangle (Smallest enclosing rectangle)
- There are two common variants of this problem.
  - In many areas of computer graphics, the bounding box (often abbreviated to bbox) is understood to be the smallest box delimited by sides parallel to coordinate axes which encloses the objects in question.
  - In other applications, such as packaging, the problem is to find the smallest box the object (or objects) may fit in ("packaged"). Here the box may assume an arbitrary orientation with respect to the "packaged" objects.
Smallest bounding sphere (Smallest enclosing sphere)
- 2-D case: Smallest bounding circle
Largest empty rectangle (Maximum empty rectangle)
Largest empty sphere
- 2-D case: Maximum empty circle (largest empty circle)