TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 13101

Computational Geometry

( Mar 03 – Mar 08, 2013 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/13101

Organizers

Contact


Schedule

Motivation

The field of computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological 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 and topological 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.

The seminar will focus on a variety of topics. We plan to have one or two in-depth presentations (60 minutes each) for these topics, accompanied by short presentations of recent work and intensive discussions.

  • 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.
  • Geometric Computing has 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.
  • Computational topology concentrates on the properties of geometric objects that go beyond metric represenation: modeling and reconstruction of surfaces, shape similarity and classification, and persistence are key concepts with applications in molecular biology, computer vision, and geometric databases.
  • In its early years, computational geometry concentrated on low dimensions. High-dimensional data come very important recently, in particular, in work related to machine learning and data analysis. Standard solutions suffer from the curse of dimensionality. This has led to extensive work on dimension-reduction and embedding techniques.
  • 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.
  • 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.

Summary

Computational Geometry and its Evolution

The field of computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological 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 and topological 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 seminar presented recent developments in the field and identified new challenges for computational geometry. Below we list some of the most interesting subareas of the field at this stage, covering both theoretical and practical issues in computational geometry.

  • 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.
  • Geometric Computing has 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.
  • Computational topology concentrates on the properties of geometric objects that go beyond metric representation: modeling and reconstruction of surfaces, shape similarity and classification, and persistence are key concepts with applications in molecular biology, computer vision, and geometric databases.
  • In its early years, computational geometry concentrated on low dimensions. High-dimensional data has become very important recently, in particular, in work related to machine learning and data analysis. Standard solutions suffer from the curse of dimensionality. This has led to extensive work on dimension-reduction and embedding techniques.
  • 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.
  • 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.

Participants

47 researchers from various countries and continents attended the seminar, showing the strong interest of the community for this event. The feedback from participants was very positive.

Dagstuhl seminars on computational geometry have been organized in a two year rhythm since a start in 1990. 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, fostering collaboration, and exposing young talent to the seniors of the field. They have arguably been the most influential meetings in the field of computational geometry.

No other meeting in our field allows young researchers to meet with, get to know, and work with well-known and senior scholars to the extent possible at Dagstuhl. To accommodate new, younger researchers, the organizers held a lottery for the first time this year. From an initial list of selected researchers, we randomly selected a certain number of senior, young, and female participants. Researchers on the initial list who were not selected by the lottery were notified by us separately per email, so that they knew that they were not forgotten, and to reassure them that-with better luck-they will have another chance in future seminars.

We believe that the lottery created space to invite younger researchers, rejuvenating the seminar, while keeping a large group of senior and well-known scholars involved. The seminar was much "younger" than in the past, and certainly more "family-friendly." Five young children roaming the premises created an even cosier atmosphere than we are used in Dagstuhl. Without decreasing the quality of the seminar, we had a more balanced attendance than in the past. Feedback from both seminar participants and from researchers who were not selected was uniformly positive.

Dagstuhl 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!

Copyright Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud

Participants
  • Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
  • Boris Aronov (Polytechnic Inst. of NYU, US) [dblp]
  • Dominique Attali (GRIPSA Lab - Saint Martin d'Hères, FR) [dblp]
  • Sang Won Bae (Kyonggi University, KR) [dblp]
  • Mikhail Belkin (Ohio State University - Columbus, US) [dblp]
  • Eric Berberich (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Kevin Buchin (TU Eindhoven, NL) [dblp]
  • Maike Buchin (TU Eindhoven, NL) [dblp]
  • Siu-Wing Cheng (HKUST - Kowloon, HK) [dblp]
  • Otfried Cheong (KAIST - Daejeon, KR) [dblp]
  • Kenneth L. Clarkson (IBM Almaden Center, US) [dblp]
  • Tamal K. Dey (Ohio State University - Columbus, US) [dblp]
  • Anne Driemel (Utrecht University, NL) [dblp]
  • Alon Efrat (University of Arizona - Tucson, US) [dblp]
  • Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Joachim Giesen (Universität Jena, DE) [dblp]
  • Marc Glisse (INRIA Saclay - Île-de-France, FR) [dblp]
  • Xavier Goaoc (INRIA Lorraine - Nancy, FR) [dblp]
  • Joachim Gudmundsson (The University of Sydney, AU) [dblp]
  • Herman J. Haverkort (TU Eindhoven, NL) [dblp]
  • Menelaos Karavelas (University of Crete - Heraklion, GR) [dblp]
  • Matthew J. Katz (Ben Gurion University - Beer Sheva, IL) [dblp]
  • Michael Kerber (Stanford University, US) [dblp]
  • Rolf Klein (Universität Bonn, DE) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Guillaume Moroz (INRIA Lorraine - Nancy, FR) [dblp]
  • Dmitriy Morozov (Lawrence Berkeley National Laboratory, US) [dblp]
  • David M. Mount (University of Maryland - College Park, US) [dblp]
  • Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
  • Marcel J. M. Roeloffzen (TU Eindhoven, NL) [dblp]
  • Günter Rote (FU Berlin, DE) [dblp]
  • Jörg-Rüdiger Sack (Carleton University - Ottawa, CA) [dblp]
  • Ludmila Scharf (FU Berlin, DE) [dblp]
  • Lena Schlipf (FU Berlin, DE) [dblp]
  • Raimund Seidel (Universität des Saarlandes, DE) [dblp]
  • Micha Sharir (Tel Aviv University, IL) [dblp]
  • Bettina Speckmann (TU Eindhoven, NL) [dblp]
  • Fabian Stehn (Universität Bayreuth, DE) [dblp]
  • Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
  • Hans Raj Tiwary (University of Brussels, BE) [dblp]
  • Suresh Venkatasubramanian (University of Utah - Salt Lake City, US) [dblp]
  • Antoine Vigneron (KAUST - Thuwal, SA) [dblp]
  • Yusu Wang (Ohio State University - Columbus, US) [dblp]
  • Carola Wenk (Tulane University - New Orleans, 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 09111: Computational Geometry (2009-03-08 - 2009-03-13) (Details)
  • Dagstuhl Seminar 11111: Computational Geometry (2011-03-13 - 2011-03-18) (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)

Classification
  • data structures / algorithms / complexity

Keywords
  • geometry
  • algorithms
  • computational topology
  • robotics
  • CAD