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:

• Thijs van Lankveld (PhD student)
• Maarten Löffler (PhD student)
• Rodrigo I. Silveira (PhD student)
• Kevin Buchin (postdoc)
• Maike Buchin (postdoc)
• dr. Marc van Kreveld (staff member)
• prof. Mark Overmars (staff member)
• dr. Frank van der Stappen (staff member)

Last Changed: Nov 1, 2005