to eAlerts

for Geom Site



What are They?

by Dan Sunday



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 geometry. 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:

Classical Geometry

Find the intersection point of two lines.

Find the circumcircle of a triangle.

Find the inscribed circle of a triangle.

Find the area of a triangle.

Find the volume of a regular 3D polyhedron.

Modern Computational Geometry

Find all intersection points of a large set of n finite line segments.

Find the smallest circumcircle of a large set of n points.

Find the largest inscribed circle inside a large set of n points.

Find the area of an irregular simple polygon with a large number of n vertices.

Find the volume of an irregular simple polytope with a large number of n vertices.

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" to refer to both classical and computational geometry algorithms.

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 instruments to construct something, 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.


© Copyright 2012 Dan Sunday, 2001 softSurfer