Overview
[Home] [Overview] [History] [Algorithms] [Books] [Web Sites] [Gift Shop]

On this page, we give an overview of what geometry algorithms are and what they are good for.  The questions we will try to answer are:

What are Geometry Algorithms ?

The easy explanation is that geometry algorithms are what a software developer programs to solve geometry problems.  And we all know what geometry problems are, right?  The simplest of such problems might be to find the intersection of two lines, the area of a given region, or the inscribed circle of a triangle.  Methods and formulas have been around for a long time to solve such simple problems.  But, when it comes to solving even these simple problems as accurate, robust, and efficient software programs, the easy formulas are sometimes inappropriate and difficult to implement.  This is the starting point for geometry algorithms as methods for representing elementary geometric objects and performing the basic constructions of classical geometry.  We refer to these as "classical geometry algorithms" implementing Euclidean, analytic, and differential geometry constructs and computations.

Recently, a new extension of geometry, now referred to as "computational geometry",  has arisen that goes beyond the scope of classical geometries.  This extension has been made possible by, and has emerged from, modern computer technology.  In short, this brand of geometry is interested in massive problems with many objects (such as large sets of points or lines).  Comparative examples of such extended problems are:

The size of the computational problem is measured by the size "n" of the large set of objects involved.  A major concern of computational geometry is to determine algorithms that are: (1) efficient even when the problem's size gets larger and larger; (2) practical and efficient for reasonably sized problems; and (3) accurate and robust on finite state computing machines.

It is somewhat inappropriate to refer to the solving of such massive geometry problems as "computational", and this has created some confusion.  In fact, classical geometry algorithms can involve more direct computation using established formulas, whereas this new brand of computer geometry is more algorithmic in nature, depending as much on the organization of the steps it performs as the actual mathematics used.  We prefer the term "algorithmic geometry", and will use it to refer to both classical and computational geometry algorithms.

It has been noted that there is nothing new about viewing geometry as algorithmic.  In fact, much of Euclid's geometry consists of algorithms to perform geometric constructions using basic operations with a straightedge and compass.  Its just that the problems were smaller since the Greek computing machine was an actual engineer using these implements to achieve the construction, and his speed was at best several operations per minute.  Modern computers can do billions of operations per second, and so the door is now open to devise algorithmic procedures for solving large scale geometric problems.

What Applications use Geometry Algorithms ?

There is a good recent (1996) Task Force Report "Application Challenges to Computational Geometry" describing many modern applications of algorithmic geometry.  It notes that with the explosion in computer graphics technology, "geometric computing is creeping into virtually every corner of science and engineering".  One could add business and finance, education, entertainment to the list.  Specific  areas that the report considers in detail include:

These are some of the areas in which geometry algorithms play a critical role.  Since everything we see and touch has a geometric aspect enabling us to understand our world, and the computer graphics and geometry ball is on the roll and gaining momentum, more-and-more areas of endeavor will start to be influenced by geometry algorithms.  You will recognize them when you see them.  But, will you know the best algorithms for new areas of application?  Knowing the fundamentals, and the scope of our current knowledge will help.

What Problems do Geometry Algorithms Solve ?

Geometry algorithms solve several classes of problems.  First, they provide fundamental methods for representing geometric objects and robustly computing primitive attributes and performing primitive operations on them.  Some of the basic problems solved by this class of algorithms are:

These are foundation algorithms that are used by a second class of higher level algorithms targeted at more specific and complex problems, such as:

What is a Good Geometry Algorithm ?

What makes a geometry algorithm good?  One factor is that it correctly solves a significant problem.  If an algorithm is the very first one or the only one to solve a certain problem, then that alone would make it significant.  Otherwise, something else has to distinguish it.  The primary theoretical  criterion used to compare algorithms is their efficiency, especially their asymptotic efficiency (aka "computational complexity") as the size n of the problem involved becomes increasingly large.  That is, the algorithm has to be ultimately faster than the competition.  Beyond speed, additional secondary criteria for good algorithms include: the amount of storage space they use, their runtime efficiency for low values of n, their ease of implementation, and also the sheer elegance of the algorithm's solution.  In some cases, the secondary criteria can outweigh the primary one.  For example, in a 1990 tour-de-force, Chazelle described a linear time O(n) algorithm for triangulating a simple polygon in the plane.  However, to this day that algorithm has never been implemented because it is too complicated!  So, other triangulation algorithms that are both reasonably fast and easy to implement become significant.  On the other hand, finding a way to simplify Chazelle's algorithm and actually programming it would be of great significance.

The asymptotic speed of an algorithm for large problem size n is measured by specifying a function f(n) such that the execution time E(n) is bounded by a constant factor times f(n); namely, E(n) < Cf(n) for some fixed constant C>0.  When f(n) is the smallest function for which this is true, one says that the algorithm is of order f(n), or is an O(f(n)) algorithm.  Commonly used bounding functions include: log n = log₂(n), n, n^k, 2ⁿ, a(n) [inverse Ackermann], l_s(n) [Davenport-Schinzel] as well as combinations of them.  An asymptotic ordering for some of these is:

a(n) < log n < log² n < ... < n < n a(n) <  n log n < n² < n³ < ... < 2ⁿ.

The following table illustrates how rapidly these functions increase.

This shows that the computing needed for an algorithm with high complexity can grow very rapidly as n gets larger.  Even for relatively small n, say n=1000, the amount of computation needed by a high complexity algorithm may be prohibitive.  Because of this, there is also a great interest in algorithms that perform well for the small values of n usually encountered in practice even if the asymptotic behavior is bad.

On the other hand, if there is a sublinear O(log n) algorithm to solve a problem, it becomes practical even for extremely large n.  The prototypical O(log n) algorithm is a binary search, and many geometry algorithms can be reduced to doing binary searches on sorted lists of geometric objects.  The sorting is often done using an O(n log n) quicksort in a preprocessing stage.  In such algorithms, the speed is divided into the preprocessing time to initialize data structures, and then the actual runtime speed with possibly many queries being made using these data structures.

Finally, it must be noted that there are resilient problems, such as the "travelling salesperson problem" (TSP), where the only known algorithms are O(2ⁿ) and it is suspected that this is the best one can do [this is the infamous "P=NP?" problem].  Since this is too much computation except for very small n, there is also a great interest in algorithms that find approximate solutions for this class of problems.

What are some Significant Geometry Algorithms ?

The past three decades have seen phenomenal advances in our knowledge about geometry algorithms.  The activity has been so great and so original that one might even consider it to be a long overdue revival.  It is more than just shaking the bones of Greek skeletons in front of us.  The massive nature of the problems involved goes as far beyond the Greeks as they went beyond the Egyptians.  Some of the most significant achievements are given in a recent (1996) report Strategic Directions in Computational Geometry.  Other notable examples are:

Copyright © 2001-2006 softSurfer.  All rights reserved.
Email comments and suggestions to feedback@softsurfer.com