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 19181

Computational Geometry

( Apr 28 – May 03, 2019 )

(Click in the middle of the image to enlarge)

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

Organizers

Contact



Schedule

Motivation

Computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological problems, which arise naturally in a wide range of areas, including computer graphics, CAD, robotics, computer vision, image processing, spatial databases, GIS, molecular biology, sensor networks, machine learning, data mining, scientific computing, theoretical computer science, and pure mathematics. Computational geometry is a vibrant and mature field of research, with several dedicated international conferences and journals and strong intellectual connections with other computing and mathematics disciplines.

The emphasis of this Dagstuhl Seminar will be on presenting recent developments in computational geometry, as well as identifying new challenges, opportunities, and connections to other fields of computing. In addition to the usual broad coverage of new results in the field, the seminar will include broad survey talks on algebraic methods in computational geometry as well as geometric data structures. The former focus area has seen exciting recent progress and the latter is a fundamental topic at the heart of computational geometry. There are numerous opportunities for further cross-disciplinary impact.

Algebraic Methods in Computational Geometry

The polynomial method of Guth and Katz of 2010 has had a fundamental impact on discrete geometry and other areas, which was already envisioned by the talk of Jiří Matoušek at the Annual European Workshop on Computational Geometry in 2011, four years before he passed away. Indeed, the polynomial method has attracted the attention of many researchers, including famous ones like Janos Pach, Micha Sharir, and Terence Tao. Applications have been found not only in making progress on long-standing combinatorial geometry problems, but also in the design and analysis of efficient algorithms for fundamental geometric problems such as range searching, approximate nearest search, diameter, etc. The polynomial method is very powerful and it offers a new research direction in which many interesting new results can potentially be discovered.

Geometric Data Structures

Many beautiful results in geometric data structures have been established in the early days of the field. Despite of this, some long-standing problems remain unresolved and some of the recent progress is in fact made using the polynomial method mentioned previously. Independently, there have been some recent advances in our understanding of lower bounds and the usage of more sophisticated combinatorial constructions and techniques such as shallow cuttings, optimal partition trees, discrete Voronoi diagrams, etc. There are also new applications that require the modeling of uncertain data and hence call for a study of the performance of geometric data structures under a stochastic setting.

Copyright Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Summary

Computational Geometry

Computational geometry is concerned with the design, analysis, and implementation of algorithms for geometric and topological problems, which arise naturally in a wide range of areas, including computer graphics, CAD, robotics, computer vision, image processing, spatial databases, GIS, molecular biology, sensor networks, machine learning, data mining, scientific computing, theoretical computer science, and pure mathematics. Computational geometry is a vibrant and mature field of research, with several dedicated international conferences and journals and strong intellectual connections with other computing and mathematics disciplines.pagebreak

Seminar Topics

The emphasis of this seminar was on presenting recent developments in computational geometry, as well as identifying new challenges, opportunities, and connections to other fields of computing. In addition to the usual broad coverage of new results in the field, the seminar included broad survey talks on algebraic methods in computational geometry as well as geometric data structures. The former focus area has seen exciting recent progress and the latter is a fundamental topic at the heart of computational geometry. There are numerous opportunities for further cross-disciplinary impact.

Algebraic Methods in Computational Geometry

The polynomial method of Guth and Katz of 2010 has had a fundamental impact on discrete geometry and other areas, which was already envisioned by the talk of Jirí Matoušek at the Annual European Workshop on Computational Geometry in 2011, four years before he passed away. Indeed, the polynomial method has attracted the attention of many researchers, including famous ones like Janos Pach, Micha Sharir, and Terence Tao. Applications have been found not only in making progress on long-standing combinatorial geometry problems, but also in the design and analysis of efficient algorithms for fundamental geometric problems such as range searching, approximate nearest search, diameter, etc. The polynomial method is very powerful and it offers a new research direction in which many interesting new results can potentially be discovered.

Geometric Data Structures

Many beautiful results in geometric data structures have been established in the early days of the field. Despite of this, some long-standing problems remain unresolved and some of the recent progress is in fact made using the polynomial method mentioned previously. Independently, there have been some recent advances in our understanding of lower bounds and the usage of more sophisticated combinatorial constructions and techniques such as shallow cuttings, optimal partition trees, discrete Voronoi diagrams, etc. There are also new applications that require the modeling of uncertain data and hence call for a study of the performance of geometric data structures under a stochastic setting.

Copyright Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Participants
  • Mikkel Abrahamsen (University of Copenhagen, DK) [dblp]
  • Peyman Afshani (Aarhus University, DK) [dblp]
  • Kevin Buchin (TU Eindhoven, NL) [dblp]
  • Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
  • Hsien-Chih Chang (Duke University - Durham, US) [dblp]
  • Siu-Wing Cheng (HKUST - Kowloon, HK) [dblp]
  • Man-Kwun Chiu (FU Berlin, DE) [dblp]
  • Arnaud de Mesmay (University of Grenoble, FR) [dblp]
  • Anne Driemel (Universität Bonn, DE) [dblp]
  • Alperen Ergür (TU Berlin, DE)
  • Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
  • Esther Ezra (Georgia Tech - Atlanta, US & Bar-Ilan Univ. Ramat Gan, IL) [dblp]
  • Kyle Jordan Fox (University of Texas - Dallas, US) [dblp]
  • Marc Glisse (INRIA Saclay - Île-de-France, FR) [dblp]
  • Rolf Klein (Universität Bonn, DE) [dblp]
  • Stefan Langerman (UL - Brussels, BE) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Wouter Meulemans (TU Eindhoven, NL) [dblp]
  • Guillaume Moroz (INRIA Nancy - Grand Est, FR) [dblp]
  • David M. Mount (University of Maryland - College Park, US) [dblp]
  • André Nusser (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Eunjin Oh (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Zuzana Patáková (IST Austria & Charles University Praha) [dblp]
  • Benjamin Raichel (University of Texas - Dallas, US) [dblp]
  • Natan Rubin (Ben Gurion University - Beer Sheva, IL) [dblp]
  • Maria Saumell (The Czech Academy of Sciences - Prague, CZ & Czech Technical University - Prague, CZ) [dblp]
  • Lena Schlipf (FernUniversität in Hagen, DE) [dblp]
  • Raimund Seidel (Universität des Saarlandes, DE) [dblp]
  • Micha Sharir (Tel Aviv University, IL) [dblp]
  • Bettina Speckmann (TU Eindhoven, NL) [dblp]
  • Monique Teillaud (INRIA Nancy - Grand Est, FR) [dblp]
  • Hans Raj Tiwary (Charles University - Prague, CZ) [dblp]
  • Marc van Kreveld (Utrecht University, NL) [dblp]
  • André van Renssen (The University of Sydney, AU) [dblp]
  • Suresh Venkatasubramanian (University of Utah - Salt Lake City, US) [dblp]
  • Kevin Verbeek (TU Eindhoven, NL) [dblp]
  • Antoine Vigneron (Ulsan National Institute of Science and Technology, KR) [dblp]
  • Birgit Vogtenhuber (TU Graz, AT) [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 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 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
  • Combinatorics
  • complexity
  • algorithms
  • geometric computing
  • implementation
  • applications
  • monitoring and shape data
  • high-dimensional computational geometry.