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.

Participants

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.

Creative Commons BY 3.0 DE

Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips

• Mikkel Abrahamsen (University of Copenhagen, DK) [dblp]
• Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
• Helmut Alt (FU Berlin, DE) [dblp]
• Elena Arseneva (St. Petersburg State University, RU) [dblp]
• Édouard Bonnet (ENS - Lyon, FR) [dblp]
• Karl Bringmann (Universität des Saarlandes - Saarbrücken, DE) [dblp]
• Mickaël Buchet (TU Graz, AT) [dblp]
• Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
• Sergio Cabello (University of Ljubljana, SI) [dblp]
• Hsien-Chih Chang (Dartmouth College - Hanover, US) [dblp]
• Siu-Wing Cheng (HKUST - Kowloon, HK) [dblp]
• Man-Kwun Chiu (FU Berlin, DE) [dblp]
• Jinhee Chun (Tohoku University - Sendai, JP) [dblp]
• Éric Colin de Verdière (University Gustav Eiffel - Marne-la-Vallée, FR) [dblp]
• Jacobus Conradi (Universität Bonn, DE)
• Arnaud de Mesmay (University Paris-Est - Marne-la-Vallée, FR) [dblp]
• Anne Driemel (Universität Bonn, DE) [dblp]
• Ioannis Emiris (University of Athens & Athena Research Center) [dblp]
• Sudeshna Kolay (Indian Institute of Technology - Kharagpur, IN) [dblp]
• Matias Korman (Siemens EDA - Wilsonville, US) [dblp]
• Joseph S. B. Mitchell (Stony Brook University, US) [dblp]
• Aleksandar Nikolov (University of Toronto, CA) [dblp]
• Steve Y. Oudot (INRIA Saclay - Île-de-France, FR) [dblp]
• Evanthia Papadopoulou (University of Lugano, CH) [dblp]
• Zuzana Patáková (Charles University - Prague, CZ) [dblp]
• Jeff M. Phillips (University of Utah - Salt Lake City, US) [dblp]
• Benjamin Raichel (University of Texas - Dallas, US) [dblp]
• Maria Saumell (The Czech Academy of Sciences - Prague & Czech Technical University in Prague, CZ) [dblp]
• Lena Schlipf (Universität Tübingen, DE) [dblp]
• Christiane Schmidt (Linköping University, SE) [dblp]
• Donald Sheehy (North Carolina State University - Raleigh, US) [dblp]
• Martin Tancer (Charles University - Prague, CZ) [dblp]
• Csaba Tóth (California State University - Los Angeles, US) [dblp]
• Uli Wagner (IST Austria - Klosterneuburg, AT) [dblp]
• Carola Wenk (Tulane University - New Orleans, US) [dblp]
• Sue Whitesides (University of Victoria, CA) [dblp]