https://www.dagstuhl.de/21181

### May 2 – 7 , 2021, Dagstuhl Seminar 21181

# Computational Geometry

## Organizers

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

## Documents

List of Participants

Shared Documents

Dagstuhl Seminar Schedule [pdf]

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

**Motivation text license**

Creative Commons BY 3.0 DE

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

## Dagstuhl Seminar Series

- 19181: "Computational Geometry" (2019)
- 17171: "Computational Geometry" (2017)
- 15111: "Computational Geometry" (2015)
- 13101: "Computational Geometry" (2013)
- 11111: "Computational Geometry" (2011)
- 09111: "Computational Geometry" (2009)
- 07111: "Computational Geometry" (2007)
- 05111: "Computational Geometry" (2005)
- 03121: "Computational Geometry" (2003)
- 01121: "Computational Geometry" (2001)
- 99102: "Computational Geometry" (1999)
- 9707: "Computational Geometry" (1997)
- 9511: "Computational Geometry" (1995)
- 9312: "Computational Geometry" (1993)
- 9141: "Computational Geometry" (1991)
- 9041: "Algorithmic Geometry" (1990)

## Classification

- Computational Geometry

## Keywords

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