Dagstuhl Seminar 11111
Computational Geometry
( Mar 13 – Mar 18, 2011 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/11111
Organizers
- Pankaj Kumar Agarwal (Duke University - Durham, US)
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE)
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR)
Contact
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Schedule
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 research remains an important issue 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 (e.g. LEDA, CGAL, CORE) have been developed. Remarkably, this emphasis on applications and implementations has emerged from the originally theoretically oriented computational geometry community itself, so many researchers are concerned now with theoretical foundations as well as implementations.
Seminar Topics
The emphasis of the seminar was on presenting the recent developments in the field as well as identifying new challenges. We have identified a few broad topics, listed below, that cover both theoretical and practical issues in computational geometry and that we believe are some of the most interesting subareas in the field.
- 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, Voronoi diagrams and nearest-neighbor data structures under various metrics have turned out to be useful for many applications and are being investigated intensively.
- Because of applications in molecular biology, computer vision, geometric databases, shape analysis has become an important topic. Not only it It raises many interesting geometric questions ranging from modeling and reconstruction of surfaces to shape similarity and classification, but it has also led to the emergence of the so-called field computational topology.
- In many applications the data lies in very high dimensional space and typical geometric algorithms suffer from the curse of dimensionality. This has led to extensive work on dimensionreduction and embedding techniques.
- Massive geometric data sets are being generated by networks of sensors at unprecedented spatial and temporal scale. How to store, analyze, query, and visualize them has raised several algorithmic challenges. New computational models have been proposed to meet these challenges, e.g., streaming model, communication-efficient algorithms, and maintaining geometric summaries.
- 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.
Participants
53 researchers from various countries and continents attended the meeting. This high number shows the strong interest of the community for this event. The feedback from participants was very positive. Dagstuhl seminars on computational geometry have been organized since 1990, lately in a two year rhythm. They have been extremely successful both in disseminating the knowledge and identifying new research thrusts. Many major results in computational geometry were first presented in Dagstuhl seminars, and interactions among the participants at these seminars have led to numerous new results in the field. These seminars have also played an important role in bringing researchers together and fostering collaboration. They have arguably been the most influential meetings in the field of computational geometry.
A session of this Seminar was dedicated to our dear friend Hazel Everett, deceased on July 20th, 2010.
The place itself is a great strength of the Seminar. Dagstuhl allows people to really meet and socialize, providing them with a wonderful atmosphere of a unique closed and pleasant environment, which is highly beneficial to interactions. Therefore, we warmly thank the scientific, administrative and technical staff at Schloss Dagstuhl!
- Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
- Oswin Aichholzer (TU Graz, AT) [dblp]
- Helmut Alt (FU Berlin, DE) [dblp]
- Victor Alvarez (Universität des Saarlandes, DE) [dblp]
- Lars Arge (Aarhus University, DK) [dblp]
- Boris Aronov (NYU Polytechnic School of Engineering, US) [dblp]
- Tetsuo Asano (JAIST - Ishikawa, JP) [dblp]
- Dominique Attali (GRIPSA Lab - Saint Martin d'Hères, FR) [dblp]
- Bernard Chazelle (Princeton University, US) [dblp]
- Otfried Cheong (KAIST - Daejeon, KR) [dblp]
- Kenneth L. Clarkson (IBM Almaden Center, US) [dblp]
- Erik D. Demaine (MIT - Cambridge, US) [dblp]
- Olivier Devillers (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Herbert Edelsbrunner (IST Austria - Klosterneuburg, AT) [dblp]
- Alon Efrat (University of Arizona - Tucson, US) [dblp]
- Esther Ezra (New York University, US) [dblp]
- Sándor Fekete (TU Braunschweig, DE) [dblp]
- Jie Gao (SUNY - Stony Brook, US) [dblp]
- Joachim Giesen (Universität Jena, DE) [dblp]
- Xavier Goaoc (INRIA Lorraine - Nancy, FR) [dblp]
- Dan Halperin (Tel Aviv University, IL) [dblp]
- Ferran Hurtado (UPC - Barcelona, ES)
- Michael Kerber (IST Austria - Klosterneuburg, AT) [dblp]
- David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
- Rolf Klein (Universität Bonn, DE) [dblp]
- Christian Knauer (Universität Bayreuth, DE) [dblp]
- Sylvain Lazard (INRIA Lorraine - Nancy, FR) [dblp]
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Joseph S. B. Mitchell (SUNY - Stony Brook, US) [dblp]
- Thomas Moelhave (Duke University - Durham, US) [dblp]
- Nabil Hassan Mustafa (LUMS - Lahore, PK) [dblp]
- János Pach (EPFL - Lausanne, CH) [dblp]
- Richard Pollack (New York University, US) [dblp]
- Saurabh Ray (MPI-SWS - Saarbrücken, DE) [dblp]
- Günter Rote (FU Berlin, DE) [dblp]
- Jörg-Rüdiger Sack (Carleton University - Ottawa, CA) [dblp]
- Michael Sagraloff (MPI für Informatik - Saarbrücken, 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 (Ben Gurion University - Beer Sheva, IL)
- Jack Snoeyink (University of North Carolina at Chapel Hill, US) [dblp]
- Bettina Speckmann (TU Eindhoven, NL) [dblp]
- Ileana Streinu (Smith College - Northampton, US) [dblp]
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Marc van Kreveld (Utrecht University, NL) [dblp]
- Suresh Venkatasubramanian (University of Utah - Salt Lake City, US) [dblp]
- Emo Welzl (ETH Zürich, CH) [dblp]
- Carola Wenk (Tulane University, US) [dblp]
- Erin Moriarty Wolf Chambers (St. Louis University, US) [dblp]
- Nicola Wolpert (University of Applied Sciences - Stuttgart, DE) [dblp]
- Chee K. Yap (New York University, US) [dblp]
- Ke Yi (HKUST - Kowloon, HK) [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 07111: Computational Geometry (2007-03-11 - 2007-03-16) (Details)
- Dagstuhl Seminar 09111: Computational Geometry (2009-03-08 - 2009-03-13) (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)
Classification
- data structures
- algorithms
- complexity
Keywords
- computational geometry
- data structures
- shape analysis
- robust algorithms
- models of computation
