Contact: Marc van Kreveld
Computational geometry is the area within algorithms research dealing with
geometric problems. Our research group has a long-standing tradition in this
area, and is one of the largest groups in the world working on it. We study
both `pure' computational-geometry problems, as well as fundamental aspects
of problems arising in application areas. Although our work in the latter
category is fundamental, we keep the applications in mind. For instance, we
try to formalize and use the characteristics of the geometry in the
application in the analysis of our solutions. This should lead to algorithms
and data structures that are provably efficient in practical situations.
Geometric computation for cartography, realistic terrain modeling, and
delineation of imprecise geographic regions all require geometric
algorithms where several geometric criteria must be met simultaneously.
Computational problems of this type are addressed by designing new exact
algorithms with efficiency analyses, and approximation algorithms with
approximation factor proofs.
The focus is on geometric algorithms for point placement (which includes
data imprecision), algorithms for realistic triangulated terrains,
and shape design problems.
For more information, see the GOGO page.
A recent development for reducing costs in industrial manufacturing is
called design for manufacturing. In a nutshell, a designer plans an object in
such a way that it can be manufactured as cheaply as possible. To make this
feasible, industrial CAD software needs to interactively provide feedback
about manufacturing options. A common manufacturing process for plastic parts
is injection molding. Liquid plastic is injected under pressure into a cavity
formed by two steel shells that are clamped together. After the plastic has
solidified, the shells are opened and the plastic part is ejected. The
difficulty is to assure that the part is not broken by the opening of the
steel cavity. A CAD-system should be able to test this, based on the
geometric model, and to warn the designer when the model is changed in a way
that makes it harder to manufacture the part. We have designed geometric
algorithms to perform such tests, considering injection molding and several
related manufacturing techniques, such as iron casting.
The geometric version of visibility in between two points amidst a set of
geometric objects is that the points see each other if and only if their
connecting straight line segment does not intersect any of the geometric
objects. Visibility has been studied extensively. For example, many versions
of the so-called art gallery problem have been considered, where visibility
within a simple polygon is the topic of study. At Utrecht University we also
consider visibility on terrains and in 3D spaces.
The following people are involved in this research area:
contact: Marc van Kreveld
Last Changed: Nov 1, 2005