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 21181

Computational Geometry

( May 02 – May 07, 2021 )

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

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 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.

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

Summary

Computational Geometry

The field of 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.

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 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 Computational Topology on Surfaces and Graphs as well as Combinatorial Complexity of Geometric Structures.

Computational 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. give 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 geq 2$, resolving a question of Danaraj and Klee in 1978. In 2017, Despré and Lazarus presented simple quasi-linear algorithms for questions regarding geometric intersection number of a curve on a surface. Progress in these and related topics have had influences in problems on graphs embedded on surfaces, maximum flows and multiple-source shortest paths in planar graphs, collapsibility of simplicial complexes, metric learning, etc. The seminar highlighted these topics with two overview talks. The first by Hsien-Chih Chang was on Tightening Curves on Surfaces, and provided a overview of recent advancements in this area, and exciting directions for future work on flipping triangulations and morphing planar multicurves using electrical moves. The second by Uli Wagner discussed Embeddability of Simplicial Compexes, and also the flurry of recent research in this area, and pinpointed the several remaining questions and where the community has not yet been able to resolve the embeddability and why the challenges remain. These talks, and other on recent advances, helped summarize the state of this area, and generate new avenues towards moving the field further forward.

Combinatorial Complexity of Geometric Structures

The understanding of the combinatorial properties of geometric structures is at the core of computational geometry. A lot of these structures such as union of shapes, cuttings, arrangements, Delaunay triangulation, Voronoi diagram have found numerous applications in algorithm design. For example, the analysis of the complexity of the union of translates of a convex body allows us to understand the complexity of the free space in planning the motion of that convex body under translation. Their studies have also triggered the development of new theoretical tools such as the polynomial method that has been gaining a lot of attention lately. There are also new applications that require the modeling of uncertain data and hence call for a study of many geometric structures under a stochastic setting. The seminar promoted these topics via two overview talks. The first overview talk was by Mikkel Abrahamsen on Minimum Fence Enclosure and Separation Problems; this line of work generalizes the notion of convex hull by identifies other minimally enclosing structures called fences, and the interesting combinatorial properties that arise. The second overview talk by Evanthia Papadopoulou was on Problems in Voronoi and Voronoi-like diagrams. This talk discussed the advancement in generalizations of the classic geometric object of Voronoi diagrams to be defined among geometric objects beyond points, and to higher-order complexes. In addition to providing snapshots of these exciting subareas, they provided future directions for research within these topics and in how they can interact across the broader computational geometry landscape.

Participants and Participation

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 and vice versa. They have arguably been the most influential meetings in the field of computational geometry. The organizers held a lottery for the fifth time this year; the lottery allows to create space to invite younger researchers, rejuvenating the seminar, while keeping a large group of senior and well-known scholars involved. The seminar has now a more balanced attendance in terms of seniority and gender than in the past. This year, 36 researchers from various countries and continents attended the seminar, despite the virtual nature due to COVID-19, showing the strong interest of the community for this event.

Due to the COVID-19 pandemic, the seminar was held entirely virtually. Talks were held over four days. Each day had 2 two-hour blocks of talks, separated by a 2-hour meal break. They were held in the late-afternoon and evening in Europe, which allowed for participants from North America to join in during their morning hours. Unfortunately, this timing was late for those in Asia. The talks were held on Zoom, a Slack server was set up for a more persistent text-based discussion, and a Wonder.me instance was arranged for dynamic forming of group discussions before and after each session. All of these settings were used to communicate research, form collaborations, and attack open problems. Although not as wonderful as actually being at Schloss Dagstuhl, these online mechanisms provided for a workable replacement for what a normal Dagstuhl seminar provides in this abnormal time.

The feedback from participants was very positive. The participants viewed the composition of the group positively, remarking how it was well-balanced in terms of seniority and gender. They also praised the quality of the talks as of very high quality - making the virtual-only participation worthwhile.

We warmly thank the scientific, administrative and technical staff at Schloss Dagstuhl! Dagstuhl made virtual hosting possible and easy in a time filled with complications. Despite not providing a physical space to meet, socialize, and collaborate, their help in organizing the event made it a success despite the less than ideal circumstances.

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

Participants
Remote:
  • 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)
  • 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)
  • 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)
  • 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]

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 19181: Computational Geometry (2019-04-28 - 2019-05-03) (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
  • Computational Geometry

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