March 16 – 21 , 2003, Dagstuhl Seminar 03121

Computational Geometry


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

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl's Impact: Documents available


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 the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.