Geometric algorithms deal with simple objects and shapes (points, lines, disks) or abstract geometric data. Unfortunately, even for classic problems on relatively simple objects, one often needs very high precision arithmetic. High-precision or symbolic computation in turn leads to significant challenges in geometric algorithm design that differ from the challenges posed by combinatorial complexity. Classic computational geometry often deals with such issues by working on an idealized machine (the so-called Real RAM model). This approach however hides most of the precision issues. In computational complexity theory there are some well-established tools as well as some recent developments that address the issue of precision head on: smoothed analysis, conditional lower bounds for approximation schemes, and ∃ℝ-completeness. Intuitively, these tools express important aspects of precision, such as robustness under tiny probabilistic perturbations, time-precision tradeoffs and whether the problem requires arbitrary algebraic numbers to be representable.

In this Dagstuhl Seminar Precision in Geometric Algorithms, we will study the precision issues that arise during the design of geometric algorithms. Three possible topics to be discussed are:

• Curved Spaces: When we consider problems in curved spaces, such as in spherical or hyperbolic geometry, then precision issues can arise easily and are largely unexplored. What is the most natural way to represent points such that distances and geometric shapes can be efficiently computed, and conversions between different models is robust?
• Geometric Graphs: Many real-world problems involve graphs that allow for geometric representations, e.g., as intersection graphs of disks, intervals, squares, etc. The associated recognition problems are often ∃ℝ -complete. In the context of precision (as well as robustness and readability/visual clarity), it is interesting to study so-called ε-robust representations where the intersection graphs remain the same even if each object may be moved to a new position of distance at most ε. In the seminar, we want to explore how ε-robustness affects algorithmic problems on geometric graphs.
• Packing: Geometric packing constitutes a vast domain within computational geometry, operations research, and pure mathematics. Recent research has shown that packing problems involving irregular objects such as convex polygons are often ∃ℝ-hard. In the seminar, we will investigate how well such problems can be approximated.

The seminar brings together researchers from the fields

• computational geometry and topology,
• approximation algorithms,
• computational complexity,
• graph algorithms and combinatorial geometry.

Our goal is to explore recent trends in rigorous precision analysis, and to find connections between the various tools used to analyze precision. We aim to identify promising new research directions as well as any blind spots in our current understanding of precision in geometric settings.

Creative Commons BY 4.0

Mikkel Abrahamsen, Sándor Kisfaludi-Bak, Linda Kleist, and Till Miltzow