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 Core problems
2 Numerical geometry
3 Non-numerical algorithms of geometry
4 Further reading
5 See also
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 takes O(n²) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(n log n). Randomized algorithms that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.

For modern GIS, computer graphics, and integrated-circuit design systems routinely handling tens and hundreds of million points, the difference between O(n²) and O(n log n) can be the difference between days and seconds of computation. Hence the emphasis on computational complexity in computational geometry.

[edit] Core problems

There are two kinds of core problems. The first one is called an algorithmic problem, where some input is given, and a corresponding output needs to be produced. Some fundamental algorithmic problems are:

Convex hull: Given a set of points, find the smallest polygon containing all the points.
Line segment intersection: Find the intersections between a given set of lines.
Delaunay triangulation: Connect a given set of points forming triangles that satisfy some fatness properties.
Voronoi diagram: Given a set of points, partition the space according to which point is closest.
Linear programming: Given a set of halfspaces, find the bottommost point contained in their intersection.
Closest pair of points: Given a set of points, find the two with the smallest distance from each other.
Polygon triangulation: Given a polygon, partition its interior by connecting its vertices.
Point in polygon: Decide whether a point is inside or outside a given polygon.

In data structuring problems, a given input needs to be preprocessed, in a way that some kind of query can be answered efficiently. The preprocessed input is called a data structure. Sometimes, other operation, like the insertion and removal of points are also allowed. Some fundamental data structuring problems are:

Range searching: Preprocess a set of points, in order to efficiently count the number of points inside a query region.
Point location: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located.
Nearest neighbor: Preprocess a set of points, in order to efficiently find which point is closest to a query point.
Ray tracing: Given a set of objects in space, produce a data structure that efficiently tells which object a query ray intersects first.

[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: