Computational geometry
|
|
In computer science, computational geometry is the study of algorithms to solve problems stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and the study of such problems is also considered to be part of computational geometry.
The main driving force for the development of computational geometry as a discipline was progress in computer graphics, computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature.
Other important "customers" of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (programming of numerically controlled (NC) machines).
There are two main flavors of computational geometry:
- Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities.
- Numerical geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling which deals primarily with representation of real-world objects in form suitable for computer computations in CAD /CAM systems.
Often, the latter kind of computational geometry is considered to be branch of computer graphics and/or CAD, and the former one is called simply computational geometry.
| Contents |
Combinatorial computational geometry
The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc.
Some of these problems look so simple that they were not regarded as problems at all until the advent of computers. Consider, for example, the Closest pair problem:
- Given N points in the plane, find two with the smallest distance from each other.
If one computes the distances between all pairs of points, there are N(N − 1)/2 of them; one then picks a pair with the smallest distance. This brute force algorithm has time complexity O(N2), i.e., its execution time is proportional to the square of the number of points. One milestone in computational geometry was the formulation of an algorithm for the closest-pair problem with time complexity O(N log N).
For modern GIS, computer graphics, and integrated circuit design systems routinely handling tens and hundreds of million points, the difference between N2 and N log N is the difference between seconds and days of computation. Hence the emphasis on computational complexity in computational geometry.
Problems
Core algorithms and problems
Problems from this list have wide applications in areas processing of geometric information is used.
- Boolean operations on polygons and polytopes
- Closest pair of points
- Convex hull
- Delaunay triangulation
- Line segment intersection
- Minimal convex decomposition
- Polygon triangulation
- Point location
- Ray casting (also known as ray tracing)
- Voronoi diagram
- Given two sets of points A and B, find the orthogonal matrix U which will minimize the distance between UA and B. In plain English, we're interested in seeing if A and B are simple rotations of one another.
Specialized problems
These are problems formulated from more specific application areas or of theoretical interest.
- Smallest bounding sphere (smallest bounding circle)
- Smallest bounding polygon
- shape dissection problems
- tessellation problems
- shape assembly problems
- shape matching problems
- The museum problem. If a museum (represented by a polygon in the plane) wants to post guards (which see in all directions) to avoid getting robbed by a crook that could in principle drop from the ceiling, it is sufficient to post a guard at each vertex. This follows from the fact that all polygons can be triangulated. However, knowing that all triangulations can be colored using only three colors (see graph coloring), we get a proof and algorithm that we never need to put more than one guard for each three vertices.
- The museum problem in three dimensions. If a museum is represented in three dimensions as a polyhedron, then putting a guard at each vertex will not ensure that all of the museum is under observation. Although all of the surface of the polyhedron would be surveyed, but there are points in the interior of the polyhedron which might not be under surveillance. (A picture of this would be good.)
- Given a list of pairs of integers (for instance, <math>\{(1,2),(1,3),(1,4),(2,5),(3,5)\}<math>) representing the edges of a graph, we can ask whether it is possible to embed this graph in the plane (that is, draw it on a flat surface) without any edges crossing. This mildly overlaps with graph theory and graph drawing, but there is a complicated algorithm to answer this question efficiently.
- Given a list of points, line segments, triangles, spheres or other convex objects, determine whether there is a separating plane, and if so, compute it.
Numerical geometry
This branch is also known as geometric modelling, computer-aided geometric design (CAGD), and may be often found under the keyword curves and surfaces.
Core problems are curve and surface modelling and representation.
The most important instruments here are parametric curves and parametric surfaces, such as Bezier curves, spline curves and surfaces. An important non-parametric approach is the level set method.
First (and still most important) application areas are shipbuilding, aircraft, and automotive industries. However because of modern ubiquity and power of computers even perfume bottles and shampoo dispensers are designed using techniques unheard of by shipbuilders of 1960s.
Books
Related topics
- Computer graphics
- CAD/CAM/CAE
- Robotics
- GIS
- Solid modelling
- Computational topology
- Algorithms
- Computational complexity
- Bounding volumede:Berechnende Geometrie
fr:Géométrie algorithmique pt:Geometria computacional sl:Računalniška geometrija zh:计算几何