https://www.dagstuhl.de/21181

02. – 07. Mai 2021, Dagstuhl-Seminar 21181

Computational Geometry

Organisatoren

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

Auskunft zu diesem Dagstuhl-Seminar erteilen

Annette Beyer zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

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

Classification

  • Computational Geometry

Keywords

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

Dokumentation

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

Publikationen

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

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.