Main Page | See live article | Alphabetical index

Computational geometry

Table of contents
1 General
2 Combinatorial Computational Geometry
3 Numerical Computational Geometry / Geometric Modeling
4 Related Links


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.

Main driving force for the computational geometry as a discipline was progress in computer graphics and in computer-aided design and manufacturing CAD /CAM, although in the hindsight some problems dealt by this discipline may be traced ages back.

Other important "customers" of computational geometry inlude 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:

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.

Combinatorial Computational Geometry

The primary reseacrh is to develop efficient algorithms and data structures for solving problems in stated in terms of most basic geometrical objects: points, line segments, polygons, polyhedra, etc.

Some of these problems look so simple that some 40 years ago they were not perceived as problems at all. Consider, for example, the following

Sure, any computer geek will tell you no big deal, compute the distances between all pairs of points (there are "only" N(N-1)/2 of them) and pick the smallest one. This "brute force" algorithm is said to have time complexity O(N2), i.e., its execution time is proportional to the squared number of the points. One of milestones in Computational geometry was an algorithm for the closest-pair problem of 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 boils down to the difference between seconds and days of computation. Hence the emphasis on computational complexity in computational geometry.

Some core algorithms:

Some computational geometry problems:

Numerical Computational Geometry / Geometric Modeling

Core problems are curve and surface modelling and representation.

The most important instruments here are parametric curves and parametric surfaces, in particular, spline curves and spline surfaces.

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.

Related Links