Computational geometry

CAD

A branch of mathematics and computer science concerned with finding efficient algorithms, or computational procedures, for solving geometric problems. Such problems can arise from computer graphics, computer-aided design, robotics and motion planning, cartography, etc. The discipline was named and largely started in the middle of the 1970s.

In its broadest sense, computational geometry is the study of geometrical problems from a computational point of view, including design and analysis of algorithms, data structures, geometric optimization, and analysis of geometric configurations. It is impossible to list all important problems and algorithms of computational geometry, and some basic concepts and results are considered below.

Voronoi diagram and Delaunay triangulation.

There are several worst-case optimal $ O ( n { \mathop{\rm log} } n ) $ algorithms for the computation of a Voronoi diagram (or Delaunay triangulation) $ { \mathop{\rm DT} } ( S ) $ of a set $ S $ of $ n $ points in the plane. For dimensions $ d > 2 $ there exist a number of efficient polynomial-time algorithms for constructing $ { \mathop{\rm DT} } ( S ) $. Many problems in computational geometry make use of $ { \mathop{\rm DT} } ( S ) $. For example, the problem of finding a closest pair of points in $ S $. One of the basic properties of the Delaunay triangulation is that if $ p _ {i} \in S $ is a nearest neighbour of $ p _ {j} $, then $ p _ {i} $ and $ p _ {j} $ are connected by an edge in $ { \mathop{\rm DT} } ( S ) $. This means one can first look for $ { \mathop{\rm DT} } ( S ) $, which is a planar graph, and subsequently locate a closest pair using the edges of this graph. As another example, the Delaunay triangulation contains all minimum spanning trees of the point set. A minimum spanning tree is a tree that connects all points of $ S $, such that the sum of the edge lengths in the tree is as small as possible. One can find a minimum spanning tree for a set $ S $ by first constructing its Delaunay triangulation.There are linear-time algorithms for extracting a minimum spanning tree from a planar graph.

See also Delaunay triangulation; Voronoi diagram.

Convex hull.

The convex hull is the most ubiquitous structure in computational geometry, surfacing in some form in almost every application. The two-dimensional problem is to compute the smallest convex polygon containing a set of $ n $ points in the plane. The optimal worst-case algorithm for solving this problem has time complexity $ O ( n { \mathop{\rm log} } n ) $. There are several efficient algorithms in higher dimensions.

There is an interesting connection between Voronoi diagrams and convex hulls, dating back to G.F. Voronoi. Through an appropriate transformation, the Voronoi diagram of a set $ S $ in $ \mathbf R ^ {d} $ corresponds to the convex hull of the transformed set in $ \mathbf R ^ {d + 1 } $. Indeed, consider the mapping $ T : {\mathbf R ^ {d} } \rightarrow {\mathbf R ^ {d + 1 } } $, $ T ( x ) = ( x, \| x \| ^ {2} ) $, which "lifts" a point $ x \in \mathbf R ^ {d} $ onto the paraboloid $ y = \| x \| ^ {2} $. Given a set $ S $ in $ \mathbf R ^ {d} $, its image under $ T $ forms the vertices of a convex polyhedron $ P $. The projection of all "downward-looking" faces of $ P $ gives precisely the faces of the Delaunay triangulation of $ S $. The relationship enables one to use convex-hull algorithms in $ d + 1 $ dimensions to obtain Delaunay triangulations in $ d $ dimensions.

Triangulation of polyhedra.

The most outstanding open problem in computational geometry has been to find a linear algorithm for triangulating a given polygon. This problem was solved in 1990 by the linear-time Chazelle triangulation algorithm.

Arrangement.

A finite collection of lines partition the plane into convex regions, edges and vertices. The resulting structure, including the incidence relations between the various pieces of the dissection, is called an arrangement of lines. Similarly, in higher dimensions an arrangement of hyperplanes may be defined. A few $ O ( n ^ {2} ) $ algorithms for constructing an arrangement of $ n $ lines have been discovered, and some of these have been generalized to an $ O ( n ^ {d} ) $ algorithm in $ d $ dimensions. These algorithms are worst-case optimal. There is a rich connection between arrangements and Voronoi diagrams.

Motion planning.

The motion planning problem in its most general form is to find a collision-free continuous motion of a fixed geometric object (a robot) between specified initial and final positions through a known cluttered environment. If the moving object is a point, this becomes a shortest path problem. Translation motion of an extended object can be reduced to the motion of a point by "making the obstacles grow" using the object via the Minkowski set difference operation (also called the Minkowski sum; cf. Addition of sets). This basic observation eventually led to $ O ( n { \mathop{\rm log} } n ) $ algorithms for moving a disc or a convex polygon in the plane with polygonal obstacles. In higher dimensions this problem is $ {\mathcal N} {\mathcal P} $- hard. For the shortest path problem on polyhedral surfaces an $ O ( n ^ {2} { \mathop{\rm log} } n ) $ algorithm has been obtained.

References

[a1]	F.P. Preparata, M.I. Shamos, "Computational geometry: an introduction" , Springer (1985)
[a2]	H. Edelsbrunner, "Algorithms in combinatorial geometry" , Springer (1987)
[a3]	J. O'Rourke, "Computational geometry" Ann. Rev. Comput. Sci. , 3 (1988) pp. 389–411
[a4]	O.R. Musin, "On some problems of computational geometry and topology" , Lecture Notes in Mathematics , 1520 , Springer (1992) pp. 57–80