Dagstuhl Seminar 03121
Computational Geometry
( Mar 16 – Mar 21, 2003 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/03121
Organizers
- Dan Halperin (Tel Aviv University, IL)
- Günter Rote (FU Berlin, DE)
Contact
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
- Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
- Hee-Kap Ahn (KAIST - Daejeon, KR) [dblp]
- Oswin Aichholzer (TU Graz, AT) [dblp]
- Helmut Alt (FU Berlin, DE) [dblp]
- Boris Aronov (Polytechnic Institute of NYU - Brooklyn, US) [dblp]
- Tetsuo Asano (JAIST - Ishikawa, JP) [dblp]
- Franz Aurenhammer (TU Graz, AT) [dblp]
- Gill Barequet (Technion - Haifa, IL) [dblp]
- Prosenjit Bose (Carleton University - Ottawa, CA)
- Hervé Brönnimann (Polytechnic Institute of NYU - Brooklyn, US)
- Beat Brüderlin (TU Ilmenau, DE)
- Guido Brunnett (TU Chemnitz, DE) [dblp]
- Sergio Cabello (University of Ljubljana, SI) [dblp]
- Aymée Calatayud Ramos (Technical University of Madrid, ES)
- Bernard Chazelle (Princeton University, US) [dblp]
- Otfried Cheong (KAIST - Daejeon, KR) [dblp]
- Sunghee Choi (University of Texas - Austin, US)
- Erik D. Demaine (MIT - Cambridge, US) [dblp]
- Tamal K. Dey (Ohio State University - Columbus, US) [dblp]
- Alon Efrat (University of Arizona - Tucson, US) [dblp]
- Ioannis Emiris (University of Athens, GR) [dblp]
- Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
- Efraim Fogel (Tel Aviv University, IL)
- Steven Fortune (Bell Labs - Murray Hill, US)
- Stefan Funke (MPI für Informatik - Saarbrücken, DE) [dblp]
- Joachim Giesen (ETH Zürich, CH) [dblp]
- Leonidas J. Guibas (Stanford University, US) [dblp]
- Hans Hagen (DFKI - Kaiserslautern, DE) [dblp]
- Dan Halperin (Tel Aviv University, IL) [dblp]
- Sariel Har-Peled (University of Illinois - Urbana-Champaign, US) [dblp]
- Ferran Hurtado (UPC - Barcelona, ES)
- Piotr Indyk (MIT - Cambridge, US) [dblp]
- Matthew J. Katz (Ben Gurion University - Beer Sheva, IL) [dblp]
- Lutz Kettner (MPI für Informatik - Saarbrücken, DE)
- David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
- Rolf Klein (Universität Bonn, DE) [dblp]
- Christian Knauer (FU Berlin, DE) [dblp]
- Vladlen Koltun (University of California - Berkeley, US) [dblp]
- Ulrich Kortenkamp (TU Berlin, DE)
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Joseph S. B. Mitchell (SUNY - Stony Brook, US) [dblp]
- Géraldine Morin (University of Toulouse, FR) [dblp]
- Mark Overmars (Utrecht University, NL)
- Sylvain Pion (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Richard Pollack (New York University, US) [dblp]
- Edgar Ramos (University of Illinois - Urbana-Champaign, US)
- Günter Rote (FU Berlin, DE) [dblp]
- Stefan Schirra (Universität Magdeburg, DE)
- Elmar Schömer (Universität Mainz, DE) [dblp]
- Raimund Seidel (Universität des Saarlandes, DE) [dblp]
- Micha Sharir (Tel Aviv University, IL) [dblp]
- Jonathan Shewchuk (University of California - Berkeley, US) [dblp]
- Shakhar Smorodinsky (New York University, US)
- Jack Snoeyink (University of North Carolina at Chapel Hill, US) [dblp]
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Marc van Kreveld (Utrecht University, NL) [dblp]
- Ron Wein (Tel Aviv University, IL)
- Emo Welzl (ETH Zürich, CH) [dblp]
- Carola Wenk (The University of Texas - San Antonio, US) [dblp]
- Nicola Wolpert (MPI für Informatik - Saarbrücken, DE) [dblp]
- Chee K. Yap (New York University, US) [dblp]
- Mariette Yvinec (INRIA Sophia Antipolis - Méditerranée, FR)
Related Seminars
- Dagstuhl Seminar 9041: Algorithmic Geometry (1990-10-08 - 1990-10-12) (Details)
- Dagstuhl Seminar 9141: Computational Geometry (1991-10-07 - 1991-10-11) (Details)
- Dagstuhl Seminar 9312: Computational Geometry (1993-03-22 - 1993-03-26) (Details)
- Dagstuhl Seminar 9511: Computational Geometry (1995-03-13 - 1995-03-17) (Details)
- Dagstuhl Seminar 9707: Computational Geometry (1997-02-10 - 1997-02-14) (Details)
- Dagstuhl Seminar 99102: Computational Geometry (1999-03-07 - 1999-03-12) (Details)
- Dagstuhl Seminar 01121: Computational Geometry (2001-03-18 - 2001-03-23) (Details)
- Dagstuhl Seminar 05111: Computational Geometry (2005-03-13 - 2005-03-18) (Details)
- Dagstuhl Seminar 07111: Computational Geometry (2007-03-11 - 2007-03-16) (Details)
- Dagstuhl Seminar 09111: Computational Geometry (2009-03-08 - 2009-03-13) (Details)
- Dagstuhl Seminar 11111: Computational Geometry (2011-03-13 - 2011-03-18) (Details)
- Dagstuhl Seminar 13101: Computational Geometry (2013-03-03 - 2013-03-08) (Details)
- Dagstuhl Seminar 15111: Computational Geometry (2015-03-08 - 2015-03-13) (Details)
- Dagstuhl Seminar 17171: Computational Geometry (2017-04-23 - 2017-04-28) (Details)
- Dagstuhl Seminar 19181: Computational Geometry (2019-04-28 - 2019-05-03) (Details)
- Dagstuhl Seminar 21181: Computational Geometry (2021-05-02 - 2021-05-07) (Details)
- Dagstuhl Seminar 23221: Computational Geometry (2023-05-29 - 2023-06-02) (Details)
- Dagstuhl Seminar 25201: Computational Geometry (2025-05-11 - 2025-05-16) (Details)
