Added to Favorites

Popular Searches

Definitions

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.## Construction/representation

## Extremal shapes

## Interaction/Search

### Proximity problems

### Visibility

## Other

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.

- 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
- Voronoi diagram

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

- Boolean operations on polygons
- Collision detection
- Line segment intersection
- Point location
- Polygon intersection
- Range searching
- Ray shooting

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

- Visibility (geometry)
- Art gallery problem (The museum problem)
- Visibility graph
- Watchman route problem
- Computer graphics applications:

- 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
- Path planning
- 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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday February 25, 2008 at 06:58:01 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday February 25, 2008 at 06:58:01 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.