Dagstuhl Seminar 09111
Computational Geometry
( Mar 08 – Mar 13, 2009 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/09111
Organizers
- Pankaj Kumar Agarwal (Duke University - Durham, US)
- Helmut Alt (FU Berlin, DE)
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR)
Contact
- Annette Beyer (for administrative matters)
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, these implementations emerged from the originally theoretically oriented computational geometry community itself, so that many researchers are concerned now with theoretical foundations as well as implementations.
The seminar focused on theoretical as well as practical issues in computational geometry. In the following, we list some of the currently most important topics in computational geometry, together with some of the leading researchers working in those areas whom were invited to this 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, pseudotriangulations, 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.
- 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.
Dagstuhl seminars on computational geometry have been organized since 1990, lately in a two year rhythm, and always have been extremely successful and on a very high scientific level, possibly the highest of all meetings on computational geometry worldwide. This year, 42 researchers from various countries and continents attended the meeting. The feedback from participants was very positive. Participants, especially junior researchers, appreciate the opportunity to meet leaders in the field and benefit from their expertise. Keeping the attendance small enough is a necessary condition for an easy communication and a good research atmosphere, but, having most leaders in the field still allows to invite some very promising younger people. This formula has been recognized as very successful for years. The long breaks in the schedule are particularly useful for research in working groups.
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!
- Mohammad Ali Abam (Aarhus University, DK) [dblp]
- 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]
- Jean-Daniel Boissonnat (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Bernard Chazelle (Princeton University, US) [dblp]
- Otfried Cheong (KAIST - Daejeon, KR) [dblp]
- Mark de Berg (TU Eindhoven, NL) [dblp]
- Erik D. Demaine (MIT - Cambridge, US) [dblp]
- Alon Efrat (University of Arizona - Tucson, US) [dblp]
- Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
- Hazel Everett (Université Nancy 2, FR)
- Esther Ezra (Duke University - Durham, US) [dblp]
- Joachim Giesen (Universität Jena, DE) [dblp]
- Sariel Har-Peled (University of Illinois - Urbana-Champaign, US) [dblp]
- Ferran Hurtado (UPC - Barcelona, ES)
- David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
- Rolf Klein (Universität Bonn, DE) [dblp]
- Christian Knauer (FU Berlin, DE) [dblp]
- Sylvain Lazard (LORIA - Nancy, FR) [dblp]
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Joseph S. B. Mitchell (SUNY - Stony Brook, US) [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]
- Daria Schymura (FU Berlin, DE)
- Raimund Seidel (Universität des Saarlandes, DE) [dblp]
- Micha Sharir (Tel Aviv University, IL) [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]
- Ileana Streinu (Smith College - Northampton, US) [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]
- Emo Welzl (ETH Zürich, CH) [dblp]
- Carola Wenk (The University of Texas - San Antonio, US) [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 07111: Computational Geometry (2007-03-11 - 2007-03-16) (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)
Classification
- computer graphics / computer vision
- data structures / algorithms / complexity
