Computational geometry

From Wikipedia, the free encyclopedia

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 impetus 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 applications 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).

The three main branches of computational geometry are:

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 representing real-world objects in forms suitable for computer computations in CAD /CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics and/or CAD, whereas the former branch is often called simply computational geometry.

Non-numerical geometry, which studies and develops non-numerical geometrical algorithms. This is the oldest branch of computational geometry which goes back to geometric constructions with the help of ruler and compass. Algorithms of geometric constructions are the soul and the origin of geometry and are not numerical in nature. Although until recently such constructions could be performed with the help of a ruler and compass only, two decades ago new means of geometric constructions emerged. These were various optical devices capable of manipulating images of geometrical figures, such as mirrors, beam splitters, holograms, etc. The observation that geometric constructions can be performed optically rather than with the help of ruler and compass laid in the foundation of "Optical Computational Geometry" put forward by Yevgeny Karasik in 1990.

1 Combinatorial computational geometry
- 1.1 Problems
  - 1.1.1 Core algorithms and problems
2 Numerical geometry
3 Non-numerical algorithms of geometry
4 See also
5 Books
6 External links

[edit] 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 seem 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 the two with the smallest distance from each other.

One could compute the distances between all the pairs of points, of which there are N(N − 1)/2, then pick the pair with the smallest distance. This brute-force algorithm has a time complexity of O(N²); 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 with the smaller 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 N² and N log N is the difference between days and seconds of computation. Hence the emphasis on computational complexity in computational geometry.

[edit] Problems

main article: List of combinatorial computational geometry topics.

[edit] 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
Binary space partitions
Closest pair of points
Convex hull
Delaunay triangulation
Line segment intersection
Linear programming
Minimal convex decomposition
Orthogonal range searching
Polygon triangulation
Point location
- Point in polygon
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.
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.

[edit] 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.

[edit] Non-numerical algorithms of geometry

See e.g. Yevgeny Karasik's "Optical Computational Geometry" in Proceedings of the 9th ACM Symposium on Computational Geometry held in Berlin, Germany in 1992:

(1992) Proceedings of the eighth annual symposium on Computational geometry. ACM Press. ISBN 0-89791-517-8 (English).

[edit] See also

[edit] Books

Edelsbrunner, Herbert (1987). Algorithms in Combinatorial Geometry. Springer-Verlag. ISBN 0-387-13722-X (English).

Goodman, J. E. and O'Rourke, J., eds. (2004). Handbook of Discrete and Computational Geometry (2nd Ed.). CRC Press. ISBN 1-58488-301-4.

Goodman, Sack, J.-R. and Urrutia, J., eds. (1998). Handbook on Computational Geometry. North Holland. ISBN 0-444-82537-1.

de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. (1997). Computational Geometry: Algorithms and Applications. Springer-Verlag. ISBN 3-540-65620-0.