Computational Geometry (Dagstuhl Seminar 21181)

Siu-Wing Cheng, Anne Driemel, Jeff M. PhillipsDagstuhl Reports 2021 · OpenReview

TL;DR

This report summarizes Dagstuhl Seminar 21181, a virtual gathering of 36 computational geometry researchers. The seminar showcased recent advancements and discussed open problems across various subfields, including computational topology, geometric structures, and fine-grained complexity, highlighting the field's continued vibrancy and its evolving focus on both theoretical foundations and practical applications.

What Problem Does This Paper Address?

This document is not a research paper in the traditional sense, but rather a report documenting the proceedings of a Dagstuhl Seminar. Dagstuhl Seminars are renowned for bringing together leading researchers to discuss the state-of-the-art, identify emerging trends, and foster collaboration. The "problem" this report addresses is the need to capture and disseminate the key discussions, presented research, and open questions from this specific seminar on Computational Geometry. The seminar itself aimed to address the ongoing challenges and opportunities within the field, which is concerned with the design, analysis, and implementation of algorithms for geometric and topological problems across a wide range of applications.

Methods

The "methods" here refer to the structure and content of the seminar itself, as documented in the report. The seminar was held virtually due to COVID-19, featuring talks that presented new results and survey existing work. These talks covered a broad spectrum of computational geometry, including:

  • Computational Topology on Surfaces and Graphs: Discussing advancements in areas like graph embeddings and simplicial complexes.
  • Combinatorial Complexity of Geometric Structures: Focusing on the underlying combinatorial properties of geometric objects and their applications.
  • Fine-grained Complexity: Investigating the theoretical limits of algorithms, often based on hypotheses like the 3-SUM or ETH.
  • Specific Algorithmic Problems: Addressing topics such as nearest neighbor search, volume approximation, and guarding problems.

The report also highlights "open problems" that emerged from the discussions, indicating areas ripe for future research.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The field is thriving and diverse: Despite being held virtually, the seminar attracted a significant number of participants, underscoring the continued interest and activity in computational geometry.
  • Bridging theory and practice: There's a clear trend towards not only developing theoretical algorithms but also considering their practical implementation and application, with a growing emphasis on software libraries.
  • Fine-grained complexity is a growing area: The seminar featured several talks on fine-grained complexity, indicating its increasing importance in understanding the fundamental limits of geometric algorithms.
  • Interdisciplinary connections are strong: Computational geometry continues to find applications and drive research in areas like computer graphics, robotics, machine learning, and scientific computing.
  • Open problems abound: The identification and discussion of open problems are a crucial outcome of such seminars, providing clear directions for future research efforts.

Key Results

This report does not present a single set of quantitative results. Instead, it summarizes the key results presented in the individual talks. For example, some talks presented:

  • Near-linear time algorithms: For problems like computing the inverse geodesic length in graphs of bounded treewidth.
  • Polynomial-time approximation algorithms: For problems like maximum independent set for rectangles in the plane.
  • New theoretical bounds: For problems related to weak epsilon-nets in higher dimensions.
  • Complexity analyses: For problems like the k-shortcut Fréchet distance, including conditional lower bounds based on ETH.

The report also lists specific open problems that were discussed, such as the twin-width of string graphs and the expected volume of stochastic bounding boxes.

Limitations and Future Work

The primary limitation acknowledged is the virtual nature of the seminar due to the COVID-19 pandemic, which, while successful in facilitating discussion, could not fully replicate the serendipitous interactions of an in-person meeting.

Future work is implicitly suggested by the numerous open problems listed throughout the report. These include:

  • Developing more efficient algorithms for various geometric problems.
  • Further exploring the theoretical limits of computation through fine-grained complexity.
  • Investigating new applications and connections to other fields.
  • Addressing specific open questions in areas like computational topology, geometric structures, and graph theory.

Summary updated

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 21181 "Computational Geometry". The seminar was held from May 2 to May 7, 2021. Because of COVID, the seminar was held online in a virtual manner, and 36 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
BibTeX
@inproceedings{cheng2021computational,
  author = {Siu-Wing Cheng and Anne Driemel and Jeff M. Phillips},
  title = {{Computational Geometry (Dagstuhl Seminar 21181)}},
  booktitle = {Dagstuhl Reports},
  year = {2021},
  url = {https://openreview.net/forum?id=YU1uL6TTu2},
}
Figure