Computational Geometry and Topology (Contributed Nugget)

How can computers help us capture, analyze, and manage geometric and
topological information?


Much of everyday science and engineering seeks answers to geometric
questions: How does this protein fold?  Can we predict a heart attack
from the heart’s motion?  Will a robot’s path plan avoid collision?
How do we derive elevation data from satellite pictures? In all cases,
the singular challenge of the task at hand is to reconcile an apparent
contradiction: geometry is continuous but algorithms handle discrete

Many geometric facts of relevance do not depend on quantitative
measurements, but rather are “topological” – asking about shape and
connectivity: that the road goes from A to B, that the blood vessels
supply blood to all vital organs, that the wall surrounds the estate,
that the rope ties the suitcase securely to the roof of the car.  The
focus on connectivity, in the small and in the large, requires a more
abstract language than the one used for measurements of lengths,
angles, and volumes.

Among the most pressing algorithmic challenges in computational
geometry and topology are the design of faster, simpler, and more
reliable techniques for searching in high-dimensional spaces, coping
with uncertainty, and reasoning at varying levels of resolution.


Computational Geometry rests on a solid foundation built in the last
three decades, which has given the community a firm grasp of the
fundamental issues arising in questions of visibility, proximity,
intersection, and multidimensional searching, as well as shape
analysis, reconstruction, and modeling.  To turn this foundational
apparatus into working solutions requiring meeting a number of
challenges, including how to reason about shapes at different levels
of resolution and how to cope with high dimensions.

While previous efforts have focused on metric considerations,
connectivity properties — the province of topology — are becoming
increasingly relevant.  Indeed, scale is at heart a topological
concept.  Here we should leave behind the simple idea of telling a
coffee cup from a bowl by its handle — even simply connected shapes
can have intricate local connectivities that determine their
properties and are critical to their functions.  Complicated organic
shapes can be characterized by monitoring their changing connectivity
as it gets simplified through thickening or other continuous
transformations.  Or think of a mountain range, whose challenges to
the explorer can be revealed by the changing connectivity of its level

The summarizing qualities of topology come to the fore when we study
high dimensions.  While spaces of dimension 4 and above are not part
of our conscious experience, they arise naturally in modeling
real-world phenomena.  For example, the motion of a rigid object in 3D
involves points in six dimensions (3 for positioning the object by
translation and 3 for rotating it suitably).  Another example is the
description of a disease, such as diabetes, as a vector of quantified
symptoms.  Collecting this data for a large population gives a cloud
of points in a space whose dimension is the number of symptoms in the
vector.  By analyzing this high-dimensional cloud, we can hope to
uncover dependencies and subtle differences that would otherwise be
hidden.  Traditional clustering methods detect isolated and
concentrated subpopulations, but fall short of suggesting dynamics in
the disease development.  To address problems of this type, computer
scientists and mathematicians are developing new forms of analyses
that find smeared-out connections, cycles, and other subtle
relationships between the subpopulations in the data.

Contributors and Credits

Bernard Chazelle and Herbert Edelsbrunner

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: