List of combinatorial computational geometry topics

From Wikipedia, the free encyclopedia

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.

Contents 1 Construction/representation 2 Extremal shapes 3 Interaction/Search 3.1 Proximity problems 3.2 Visibility 4 Other

[edit] Construction/representation

• Convex hull
• Happy end problem
• Hyperplane arrangement
• Polygon decomposition
  • Polygon triangulation
    • Minimal convex decomposition
    • Minimal convex cover problem (NP-hard)
    • Minimal rectangular decomposition
  • Tessellation problems
• Shape dissection problems
• Straight skeleton
• Stabbing line problem
• Triangulation
  • Delaunay triangulation
  • Point set triangulation
  • Polygon triangulation
• Voronoi diagram

[edit] Extremal shapes

• Smallest bounding sphere (Smallest enclosing sphere)
  • Smallest bounding circle
• Smallest enclosing box (Smallest bounding box)
  • Smallest bounding rectangle (Smallest enclosing rectangle)
• Maximum empty rectangle
• Maximum empty circle
• Minimum bounding box

[edit] Interaction/Search

• Boolean operations on polygons
• Collision detection
• Line segment intersection
• Point location
  • Point in polygon
• Polygon intersection
• Range searching
  • Orthogonal range searching
  • Simplex range searching
• Ray shooting

[edit] Proximity problems

• Closest pair of points
• Closest point problem
• Diameter of a point set
• Delaunay triangulation
• Voronoi diagram

[edit] Visibility

• Visibility (geometry)
• Art gallery problem (The museum problem)
• Visibility graph
• Watchman route problem
• Computer graphics applications:
  • Hidden surface determination
  • Hidden line removal

[edit] Other

• Ray casting (also known as ray tracing)
• 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