28. April – 03. Mai 2019, Dagstuhl-Seminar 19181

Computational Geometry


Siu-Wing Cheng (HKUST – Kowloon, HK)
Anne Driemel (Universität Bonn, DE)
Jeff Erickson (University of Illinois – Urbana-Champaign, US)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 9, Issue 4 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


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.

Summary text license
  Creative Commons BY 3.0 Unported license
  Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Dagstuhl-Seminar Series


  • Data Structures / Algorithms / Complexity


  • Combinatorics
  • Complexity
  • Algorithms
  • Geometric computing
  • Implementation
  • Applications
  • Monitoring and shape data
  • High-dimensional computational geometry.


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.