Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 07111

Computational Geometry

( Mar 11 – Mar 16, 2007 )

Please use the following short url to reference this page:



The field of computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric problems, which arise in a wide range of areas, including computer graphics, CAD, robotics computer vision, image processing, spatial databases, GIS, molecular biology, and sensor networks. Since the mid 1980s, computational geometry has arisen as an independent field with its own international conferences and journals.

In the early years mostly theoretical foundations of geometric algorithms were laid, and fundamental theoretical questions remain an important topic in the field. Meanwhile, as the field matured, researchers have started paying close attention to applications and implementations of geometric algorithms. Several software libraries for geometric computation have been developed. Remarkably, these implementations emerged from the originally theoretically oriented computational geometry community itself. Consequently, many researchers are now concerned with theoretical foundations as well as implementation issues.

The seminar will focus on theoretical as well as practical issues in computational geometry. Some of the currently most important topics in computational geometry will be addressed in the seminar:

  • Theoretical foundations of computational geometry lie in combinatorial geometry and its algorithmic aspects. They are of an enduring relevance for the field, particularly the design and the analysis of efficient algorithms require deep theoretical insights.
  • Various applications such as robotics, GIS, or CAD lead to interesting variants of the classical topics originally investigated, including convex hulls, Voronoi diagrams and Delaunay triangulations, and geometric data structures. For example, pseudo triangulations, generalization of triangulations and developed in connection with visibility and shortest-path problems, have turned out to be useful for many other applications and are being investigated intensively.
  • Because of applications in molecular biology, computer vision, geometric databases, shape analysis has become an important topic.
  • Another increasingly important application of computational geometry is modeling and reconstruction of surfaces. It brings about many interesting questions concerning fundamental structures like triangulations as well as new issues in computational topology.
  • Implementation issues have become an integral part of the research in computational geometry. Besides general software design questions especially robustness of geometric algorithms is important. Several methods have been suggested and investigated to make geometric algorithms numerically robust while keeping them efficient, which lead to interaction with the field of computer algebra, numerical analysis, and topology.

Dagstuhl seminars on computational geometry have been organized since 1990, in a two year rhythm in the recent years, have always been very successful in both disseminating the recent research and conceiving the new ideas.

Parallel to our seminar a second one on Cutting, Packing, Layout and Space Allocation will be organized in Dagstuhl. Because of the overlap of both topics there certainly will be talks in the one seminar which are of interest to the other group, as well. In addition, there should be a beneficial exchange of problems and ideas between both groups. Therefore, the groups of organizers of both seminars agreed to give participants the opportunity to move freely between the two seminars and to have at least one common session.

  • Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
  • Oswin Aichholzer (TU Graz, AT) [dblp]
  • Helmut Alt (FU Berlin, DE) [dblp]
  • Lars Arge (Aarhus University, DK) [dblp]
  • Boris Aronov (NYU Polytechnic School of Engineering, US) [dblp]
  • Tetsuo Asano (JAIST - Ishikawa, JP) [dblp]
  • Franz Aurenhammer (TU Graz, AT) [dblp]
  • Otfried Cheong (KAIST - Daejeon, KR) [dblp]
  • Kenneth L. Clarkson (IBM Almaden Center, US) [dblp]
  • Mark de Berg (TU Eindhoven, NL) [dblp]
  • Erik D. Demaine (MIT - Cambridge, US) [dblp]
  • Tamal K. Dey (Ohio State University - Columbus, US) [dblp]
  • Scot Drysdale (Dartmouth College - Hanover, US)
  • Alon Efrat (University of Arizona - Tucson, US) [dblp]
  • Esther Ezra (New York University, US) [dblp]
  • Joachim Giesen (Universität Jena, DE) [dblp]
  • Leonidas J. Guibas (Stanford University, US) [dblp]
  • Thomas Hackl (TU Graz, AT)
  • Dan Halperin (Tel Aviv University, IL) [dblp]
  • Clemens Huemer (UPC - Barcelona, ES)
  • Ferran Hurtado (UPC - Barcelona, ES)
  • Piotr Indyk (MIT - Cambridge, US) [dblp]
  • Lutz Kettner (NVIDIA GmbH - Berlin, DE)
  • David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
  • Rolf Klein (Universität Bonn, DE) [dblp]
  • Christian Knauer (Universität Bayreuth, DE) [dblp]
  • Hannes Krasser (TU Graz, AT)
  • Stefan Langerman (University of Brussels, BE) [dblp]
  • Ulrich Lauther (Siemens AG - München, DE) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Joseph S. B. Mitchell (SUNY - Stony Brook, US) [dblp]
  • János Pach (EPFL - Lausanne, CH) [dblp]
  • Richard Pollack (New York University, US) [dblp]
  • Günter Rote (FU Berlin, DE) [dblp]
  • Jörg-Rüdiger Sack (Carleton University - Ottawa, CA) [dblp]
  • Ludmila Scharf (FU Berlin, DE) [dblp]
  • Raimund Seidel (Universität des Saarlandes, DE) [dblp]
  • Jonathan Shewchuk (University of California - Berkeley, US) [dblp]
  • Jack Snoeyink (University of North Carolina at Chapel Hill, US) [dblp]
  • Bettina Speckmann (TU Eindhoven, NL) [dblp]
  • Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
  • Marc van Kreveld (Utrecht University, NL) [dblp]
  • Kasturi R. Varadarajan (University of Iowa - Iowa City, US) [dblp]
  • Antoine Vigneron (INRA - MIA - Jouy-en-Josas, FR) [dblp]
  • Yusu Wang (Ohio State University - Columbus, US) [dblp]
  • Emo Welzl (ETH Zürich, CH) [dblp]
  • Nicola Wolpert (University of Applied Sciences - Stuttgart, DE) [dblp]

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 03121: Computational Geometry (2003-03-16 - 2003-03-21) (Details)
  • Dagstuhl Seminar 05111: Computational Geometry (2005-03-13 - 2005-03-18) (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)

  • data structures / algorithms / complexity
  • computer graphics / computer vision

  • computational geometry
  • triangulations
  • Voronoi diagrams
  • combinatorial geometry
  • robustness
  • shape