16. – 21. März 2003, Dagstuhl-Seminar 03121

Computational Geometry


Dan Halperin (Tel Aviv University, IL)
Günter Rote (FU Berlin, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl's Impact: Dokumente verfügbar


Geometric computing is present in virtually every corner of science and engineering, from computer-aided design and manufacturing to cartography and structural molecular biology. For over two decades, Computational Geometry has supplied the solid foundation for the study of algorithms which are relevant to all these areas.

Traditionally, Computational Geometry has treated linear objects like line segments or polygons, occasionally also circles and ellipses or other special shapes. For many novel applications, it is important to handle more general curves or surfaces that might be given as splines or in a general parametric form. Such shapes should be handled by algorithms directly, not only by piecewise linear approximation as has been done so far. Examples of applications that will benefit from extending the Computational Geometry repertoire to curved objects are: robot motion planning with many degrees of freedom (as has been demonstrated in the seminar), advanced manufacturing techniques involving micro manipulation and assembly, and computer-aided surgery, to name a few. Considerable portion of the seminar was dedicated to presenting and discussing recent progress in geometric computing with curves and surfaces.

Twelve talks dealt with this topic, ranging from special number types to support the robust handling of curved objects through algorithmic techniques to implemented systems (talks by Yvinec, Teillaud, Emiris, Mehlhorn, Wolpert, Wein, Halperin, Morin, Demaine, Fortune, Calatayud, and Schirra).

Another perspective on similar issues has been provided by several invitees from the area of Geometric Modeling and CAGD (talks by Brüderlin, Brunett, Hagen). This was nicely complemented by talks on modeling techniques in curve and surface reconstruction by Giesen, Dey and Ramos. Straddling both Computational Geometry and Computer-Aided Geometric Design was the talk by Morin, who described the joint work with Knauer on geometric filtering for parametric curves.

Additional topics were applications in wireless communication (talks by Smorodinsky and Funke), meshing (talk by Shewchuk), geometric optimization problems with applications to cartography, metrology, and other areas (talks by Barequet, Brönniman, van Kreveld, Har-Peled, Cabello, Mitchell, and Efrat), the geometry of lines in space (talks by Cheong, Koltun), and large kinematic structures with applications to molecular simulation and robot motion planning (talks by Agarwal, Knauer, and Guibas).

Novel perspectives on algorithms for geometric problems were proposed by Bernard Chazelle, who presented an approach for solving geometric problems in sub-linear time, without looking at the whole data, and Chee Yap on a new general framework of pseudo-approximation algorithms.

There was an unusually large number of participants (67), many of whom gave presentations about their latest results (46 presentations), lasting 10-30 minutes. Still, there was ample time for scientific discussions and social interaction during the extensive lunch breaks, in the evenings, and during the excursion on Wednesday afternoon. Special care was taken to give younger participants the opportunity for presentations and to get them involved in the discussions.

During the seminar, there was a meeting of representatives of the CGAL (Computational Geometry Algorithms Library) group to coordinate work on arrangements of curves. Several key issues in implementing arrangements of curves were clarified and resolved by the shared experience of all sites.

An open problem session was held on Monday night. It lasted two hours and additionally stimulated the discussions during the workshop. Some problems were solved during the week or even right at the problem session. A list of open problems was collected.

On Wednesday afternoon, a bus trip to the Saarschleife (loop of the river Saar) and to Mettlach was offered. One group walk from the tip of the Saarschleife to Mettlach along the river; another group went to Mettlach by bus to see the "Keravision" exhibition of Villeroy & Boch, the ceramics and pottery factory which is located there. The weather was exceptionally nice during the whole week, with fresh temperatures but almost continuous sunshine (during the day).

The participants and organizers of this workshop would like to thank the Dagstuhl office and the local personnel for the engaged and competent support in all matters. The cordial atmosphere provided for an unusually successful and enjoyable workshop.

Open Problems

List of open Problems

Dagstuhl-Seminar Series


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.