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
- Boolean operations on polygons
- Convex hull
- Hyperplane arrangement
- Polygon decomposition
- * Polygon triangulation
- ** Minimal convex decomposition
- ** Minimal convex cover problem
- ** Minimal rectangular decomposition
- * Tessellation problems
- Shape dissection problems
- Straight skeleton
- Stabbing line problem
- Triangulation
- * Delaunay triangulation
- * Point-set triangulation
- * Polygon triangulation
- Voronoi diagram
Extremal shapes
- Minimum bounding box
- * 2-D case: Smallest bounding rectangle
- * There are two common variants of this problem.
- ** In many areas of computer graphics, the bounding box 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 may fit in. Here the box may assume an arbitrary orientation with respect to the "packaged" objects.
- Smallest bounding sphere
- * 2-D case: Smallest bounding circle
- Largest empty rectangle
- Largest empty sphere
- * 2-D case: Maximum empty circle
Interaction/search
- Collision detection
- Line segment intersection
- Point location
- * Point in polygon
- Polygon intersection
- Range searching
- * Orthogonal range searching
- * Simplex range searching
- Ray casting
- Slab method
[Proximity problems]
- Closest pair of points
- Closest point problem
- Diameter of a point set
- Delaunay triangulation
- Voronoi diagram
Visibility
- Visibility (geometry)
- Art gallery problem
- Visibility graph
- Watchman route problem
- Computer graphics applications:
- * Hidden surface determination
- * Hidden line removal
- Ray casting
Other
- Happy ending problem
- Ham sandwich problem
- shape assembly problems
- shape matching problems
- Klee's measure problem
- Problems on isothetic polygons and isothetic polyhedra
- *Orthogonal convex hull
- Path planning
- * Paths among obstacles
- *Shortest path in a polygon
- Polygon containment
- Robust geometric computation addresses two main issues: fixed-precision representation of real numbers in computers and possible geometrical degeneracy (mathematics) of input data
Computational geometry
Computational geometry
Category:Mathematics-related lists