May 2 – 7 , 2021, Dagstuhl Seminar 21181

Computational Geometry


Siu-Wing Cheng (HKUST – Kowloon, HK)
Anne Driemel (Universität Bonn, DE)
Jeff M. Phillips (University of Utah – Salt Lake City, US)

For support, please contact

Annette Beyer for administrative matters

Michael Gerke for scientific matters

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.


List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule [pdf] (Update here)

(Use personal credentials as created in DOOR to log in)


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 the seminar is 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 with a special focus on two areas. First, computational topology on surfaces and graphs. This area has seen exciting recent progress. Second, proximity and geometric networks, which are fundamental topics at the heart of computational geometry.

Topology on Surfaces and Graphs

Computational topology has seen exciting advances in a number of topics. Indeed, best paper awards in several recent SoCGs went to papers on these topics. In 2019, Cohen-Addad et al. gave a lower bound to a cutting problem in embedded graphs, essentially matching the running time of the fastest algorithm known and settling a 17-year old question. In 2018, Goaoc et al. proved that it is NP-complete to decide if a d-dimensional simplicial complex is shellable for d > 1, resolving a question of Danaraj and Klee in 1978. In 2017, Despré and Lazarus presented simple quasi-linear algorithms for questions regarding the geometric intersection number of a curve on a surface. Progress in these and related topics has had influence in problems on graphs embedded on surfaces, maximum flows and multiple-source shortest paths in planar graphs, collapsibility of simplicial complexes, metric learning, etc. There are opportunities for many interesting new results to be discovered.

Proximity and Geometric Networks

The understanding of nearness of geometric objects underlies most of data analysis, and is what gives structure that is essential to most of computational geometry. Recently the computational geometry community has made significant progress on many of these topics, both from combinatorial analysis of objects like the Voronoi diagram, allowing for data structures with complex queries, or bounding the higher-level structure of the geometry networks they induce. These approaches have developed a deeper understanding of the interplay between the underlying geometric complexity and the algorithmic implications this structure allows. These results have numerous applications in algorithmic design beyond just computational geometry.


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. The organizers hold a lottery to create space to invite less senior researchers, while keeping a large group of senior and well-known scholars involved.

Motivation text license
  Creative Commons BY 3.0 DE
  Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips

Dagstuhl Seminar Series


  • Computational Geometry


  • Computational Geometry
  • Geometry
  • Topology
  • Discrete Geometry
  • Combinatorics
  • Complexity
  • Algorithms
  • Geometric computing
  • Data structures

Book exhibition

Books from the participants of the current Seminar

Book exhibition in the library, ground floor, during the seminar week.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.