Precision in Geometric Algorithms

Hyperbolic geometry is a non-Euclidean geometry where the parallel axiom is negated. While the hyperbolic plane behaves locally like the Euclidean plane, it behaves very different beyond that. One crucial difference is that the hyperbolic plane expands exponentially. This has various interesting effects for studying graphs in the hyperbolic plane. When embedding graphs into the hyperbolic plane, the exponential expansion can be used to, for example, achieve successful greedy routing. Moreover, when defining graphs from geometric objects, like intersection graphs of equally sized disks, the properties of the hyperbolic plane translate to interesting graphs properties.

Imprecise measurements of a point set $P=(p_1,\mathrm{\dots },p_n)$ can be modelled by a family of regions $F=(R_1,\mathrm{\dots },R_n)$, where each imprecise region $R_i\in F$ contains a unique point $p_i\in P$. A retrieval models an accurate measurement by replacing an imprecise region $R_i$ with its corresponding point $p_i$.

We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of $P$ as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved.

Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let $r(F,P)$ denote the minimal number of retrievals required by any algorithm to determine the convex hull of $P$ for a given instance $(F,P)$. For a family $F$ of $n$ constant-complexity polygons, our main result is a reconstruction algorithm that performs $\mathrm{\Theta }(r(F,P))$ retrievals in $O(r(F,P){\log }^{3}n)$ time.

Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple $k$-gons, to pairwise disjoint disks with radii in $[1,k]$, and to unit disks where at most $k$ disks overlap in a single point. Our runtime scales linearly with $k$.

Penny graphs are contact graphs of unit disks in the plane. We show that recognizing penny graphs is ER-complete, that is as hard as deciding truth in the existential theory of the reals. The problem remains ER-complete even if a combinatorial embedding of the penny graph is given. Penny graphs which are trees can be realized with the centers of the pennies belonging to a grid of double-exponential size. We can also show that recognizing marble graphs, contact graphs of unit balls in three-dimensional space, is ER-complete.

While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real computation models is more adequate. For example, when working with continuous probability distributions for say smoothed analysis, in continuous optimization, computational geometry or machine learning. We want to compare real models of computation with discrete models of computation. We do this by means of oracle separation results.

We define the notion of a real Turing machine as an extension of the (binary) Turing machine by adding a real tape. Using those machines, we define and study the real polynomial hierarchy $ℝ\text{PH}$. We are interested in $ℝ\text{PH}$ as the first level of the hierarchy corresponds to the well-known complexity class $\exists ℝ$. It is known that $\text{NP}\subseteq \exists ℝ\subseteq \text{PSPACE}$ and furthermore $\text{PH}\subseteq ℝ\text{PH}\subseteq \text{PSPACE}$. We are interested to know if any of those inclusions are tight. In the absence of unconditional separations of complexity classes, we turn to oracle separation. We develop a technique that allows us to transform oracle separation results from the binary world to the real world. As applications, we show there are oracles such that:

• $\mathrm{■}$

  $ℝ{\text{PH}}^O$ proper subset of ${\text{PSPACE}}^O$,

• $\mathrm{■}$

  $BQ{P}^O$ not contained in $ℝ{\text{PH}}^O$.

Our results hint that $\exists ℝ$ is strictly contained in PSPACE and that there is a separation between the different levels of the real polynomial hierarchy. We also bound the power of real computations by showing that NP-hard problems are unlikely to be solvable using polynomial time on a realRAM. Furthermore, our oracle separations hint that polynomial-time quantum computing cannot be simulated on an efficient real Turing machine.

Abstract: Let $S$ and $T$ be two sets of points in a metric space with a total of $n$ points. Each point in $S$ and $T$ has an associated value that specifies an upper limit on how many points it can be matched with from the other set. A multimatching between $S$ and $T$ is a way of pairing points such that each point in $S$ is matched with at least as many points in $T$ as its assigned value, and vice versa for each point in $T$. The cost of a multimatching is defined as the sum of the distances between all matched pairs of points. The geometric multimatching problem seeks to find a multimatching that minimizes this cost. A special case where each point is matched to at most one other point is known as the geometric many-to-many matching problem.

We present two results for these problems when the underlying metric space has a bounded doubling dimension. Specifically, we provide the first near-linear-time approximation scheme for the geometric multimatching problem in terms of the output size. Additionally, we improve upon the best-known approximation algorithm for the geometric many-to-many matching problem, previously introduced by Bandyapadhyay and Xue (SoCG 2024), which won the best paper award at SoCG 2024.

The X-Y art-gallery problem asks to find a minimum set of guards that guard a polygon $P$, where the guards are restricted to lie in X and must see all of Y. For X,Y$\in \{$Point, Boundary, Vertex$\}$, this gives $9$ different variants. Recent work has determined the complexity of each of these variants; all but the Boundary-Boundary variant were known to be either NP-complete or $\exists ℝ$-complete.

We complete this classification, showing that the Boundary-Boundary variant is NP-complete. This is somewhat surprising, since the coordinates of guards in an optimal solution might need to be irrational. We show that each coordinate is at worst $p+q\sqrt{r}$, where $p$, $q$ and $r$ are rational numbers with polynomially many bits. These coordinates give a certificate that can be verified in polynomial time.

We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon and further improved by Chang et al. obtained Steiner $(1+\epsilon )$-spanners of size $O_d({\epsilon }^{(1-d)/2}\log (1/\epsilon )n)$, nearly matching the lower bounds of Bhore and Tóth.

We obtain Steiner $(1+\epsilon )$-spanners of size $O_d({\epsilon }^{(1-d)/2}\log (1/\epsilon )n)$ not only in $d$-dimensional Euclidean space, but also in $d$-dimensional spherical and hyperbolic space. For any fixed dimension $d$, the obtained edge count is optimal up to an $O(\log (1/\epsilon ))$ factor in each of these spaces. Unlike earlier constructions, our Steiner spanners are based on simple quadtrees, and they can be dynamically maintained, leading to efficient data structures for dynamic approximate nearest neighbours and bichromatic closest pair.

In the hyperbolic setting, we also show that $2$-spanners in the hyperbolic plane must have $\mathrm{\Omega }(n\log n)$ edges, and we obtain a $2$-spanner of size $O_d(n\log n)$ in $d$-dimensional hyperbolic space, matching our lower bound for any constant $d$. Finally, we give a Steiner spanner with additive error $\epsilon$ in hyperbolic space with $O_d({\epsilon }^{(1-d)/2}\log (\alpha (n)/\epsilon )n)$ edges, where $\alpha (n)$ is the inverse Ackermann function.

Our techniques generalize to closed orientable surfaces of constant curvature as well as to some quotient spaces.

Given $k$ polygonal curves $c_1,\mathrm{\dots },c_k$ in the plane or in some higher-dimensional space with endpoints $s_i,t_i$ and $k$ point robots $r_1,\mathrm{\dots },r_k$, each robot $r_i$ has to move from $s_i$ to $t_i$ with its center constrained to $c_i$, without backtracking. The objective is to compute a coordinated motion that minimizes the maximum pairwise distance between robots along their trajectories.

For $k=2$, this is the classic Fréchet distance. The problem formulation can be generalized in various ways, some of which are motivated by applications in robotics and transportation. These include minimum clearance conditions or collisions avoidance (the easiest case being circular robots), and alternative objective functions, several of which give rise to especially challenging variants of the problem.

We worked on a new complexity class denoted by $\text{Q}ℝ$. This complexity class can be defined as all problems that are equivalent to deciding the First Order Theory of the Reals. We describe a framework to show $\text{Q}ℝ$-completeness of Devil’s games. Devil’s games have two key properties.

• $\mathrm{■}$

  Players alternate in taking turns and

• $\mathrm{■}$

  each turn gives an infinite continuum of possible turns.

There is this very cute classical puzzle, which goes as follows: After a career of elegant proofs occasionally sabotaged by overlooked edge cases, you find yourself in hell’s quiet reading room, where the devil greets repentant theoreticians with a friendly smile. He gestures to a round table and proposes a simple challenge: you and he will take turns placing identical coins on the tabletop, and coins may not overlap. Whoever cannot place a new coin on the table loses. The devil insists you move first, confident that impatience will cloud your reasoning just as it did in life. Win, and he’ll grant you a brief return to correct that final paper; lose, and you will spend eternity proofreading the edge cases of others. Interestingly if you place your first coin precisely at the center and then mirror every move of the devil across that center, you can always respond and never be the one to run out of space first. This idea uses symmetry and is a standard technique in combinatorial game theory. But note, if you had not placed the first coin in the middle. It seems impossible to analyze how to win this game. The reasons being the two defining properties of Devil’s games. While there are plenty of results that show that combinatorial games are PSPACE-complete, this seems not to capture the second aspect of the Devil’s game. And intuitively the second property makes Devil game’s quite distinct from most other known combinatorial games. This intuition motivates us to study Devil’s games more broadly. We use the term Devil’s games, for two reasons. One is a reference to the old puzzle from above and the second is that they are devilishly difficult to analyze.

The topic of this working group was to study the realization spaces of simple graphs (paths, trees or cycles) when representing them geometrically in two and three dimensions. A main motivation for this was to complement the recent results of Lubiw and Schaefer that imply universality for the realization spaces of penny and marble graphs in general. More precisely, we have investigated the following problems.

We study the packing of convex polygons in the online setting. Here, convex polygons (a total of $n$ in number) arrive one by one, and need to be packed (immediately and irrevocably, using translation and without overlapping) in a horizontal unbounded strip of unit height. Our goal is to minimize the width of the strip to pack all polygons. We have some promising initial results that might lead to a ${(\log n)}^{O(1)}$-competitive algorithm. Our approach exploits connections with the online sorting problem, where $n$ elements are revealed one by one and have to be placed in an immediate and irrevocable manner into empty cells of an array. The objective is to minimize the sum of absolute differences between elements in the consecutive cells. We also hope to extend the approach to obtain a ${(\log n)}^{O(d)}$-competitive algorithm for packing $d$-dimensional convex polytopes into a $d$-dimensional strip (with $(d-1)$-dimensional unit cube base and unbounded length in the $d$-th dimension).

Let $P$ be a set of points in the Euclidean plane (or more generally, in ${ℝ}^d$. Consider an edge weighted graph $G=(P\cup S,E),w:E\to {ℝ}_{\ge 0}$ and let ${\mathrm{dist}}_{G,w}$ be the induced shortest-path distance. If for some $>0$ the distance ${\mathrm{dist}}_{G,w}$ satisfies for all $u,v\in P$ that

then $(G,w)$ is called a $(1+\epsilon )$-emulator and the points of $S$ are called Steiner vertices. Our goal in this problem has been to minimize the number of edges in the emulator.

The variant of the problem where $S\subset {ℝ}^d$ and the weight function is forced to be the Euclidean weight function is well-understood: the resulting graphs are called Steiner spanners, and the sparsest possible Steiner spanners in ${ℝ}^d$ are known to have $\mathrm{\Theta }(n/{\epsilon }^{\frac{d-1}{2}})$ edges up to logarithmic factors of $1/\epsilon$.

During the seminar, we started working on the specific point set $P$ that is used in the lower bound for Euclidean Steiner spanners: this corresponds to a bipartite setting. The bipartite construction can be used as a basis for general constructions, and the best Euclidean construction is simply the complete bipartite graph, so it should be possible to improve to find a sparser graph using emulators where we have more freedom to choose the edge weights. We have identified several structural properties of a potential edge-minimal solution based on the geometric constraints, and have found some examples of graphs that had fewer edges than the complete bipartite graph. Deciding if these constructions can be assigned the desired weights is a work in progress.

At Dagstuhl, we worked on the “Flip Distance to a Geometric Crossing-Free Perfect Matching” problem, which we informally called “Uncrossing Line Segments”. In this problem, you are given a set of 2n points in the plane and a perfect matching of them. You create a line segment between any two matched points, which gives a configuration of n line segments. Some of these line segments may intersect. We want to transform the instance into one without any intersections using the “flip” operator. Practically, we may “flip” two crossing line segments, and match the four points involved in these line segments in the other two possible ways, neither of which will cause these two lines to intersect. Prior to the seminar, the best known results were that there exists a configuration that always takes $\mathrm{\Omega }(n)$ flips to uncross, all configurations have a sequence of $O(n^2)$ flips to uncross them, and an adversary can take at most $O(n^3)$ flips on any configuration. Additionally, unbeknownst to us, it was also known that if the points are in convex position, there is always a sequence of $O(n)$ flips to uncross it.

During the seminar, we did not manage to make much progress on the problem. Our main novel result is that if there are $k$ points not on the convex hull of the pointset, then there exists a sequence of $O(nk)$ flips to uncross the configuration. Otherwise, we looked into many potential-based strategies to keep track of the ‘progress’ we make upon performing a specific flip; we looked into search trees; into the dual; into divide and conquer strategies; and many more subideas.

A hyperbolic uniform disk graph (HUDG) is the intersection graph of disks of equal radius $r$ in the hyperbolic plane. Recognizing HUDGs is $\exists ℝ$ complete. However, the hardness is essentially based on the fact that Euclidean UDGs are a subclass of HUDGs. One way of looking at a subset of HUDGs that are very hyperbolic are strongly hyperbolic UDGs: here all vertices have to be placed into a disk of radius at most $2r$.

Question: Is recognizing SHUDGs in NP (or even in P)? It might be interesting to restrict SHUDGs further to only sparse graphs. An alternative way of restricting HUDGs to graphs that are rather hyperbolic is to require $r\in \mathrm{\Omega }(\log n)$.

A polygonal knot⁵⁵5This terminology is nonstandard, don’t google it. is a closed polygonal curve in ${ℝ}^3$. Two polygonal knots made of $k$ segments are isotopic if there is a continuous (non-necessarily polygonal) deformation from one to the other without crossings, and are polygonally isotopic if there is such a deformation that respects the polygonal structure, i.e., such that all the intermediate curves are also polygonal knots with $k$ segments. The lengths of the segments do not have to be respected.

Consider the following distance problems:

1. Pr1

   Given a set of open convex pairwise disjoint obstacles in ${ℝ}^3$ and $a,b\in {ℝ}^3$, find the shortest path connecting $a$ and $b$ that avoids the obstacles.

2. Pr2

   Given a polygonal surface (e.g., boundary of a $3$-dimensional convex polyhedron, but could be just an abstract surface), find its diameter.

3. Pr3

   Given a set of (integer) points in ${ℝ}^3$, find the shortest tree connecting them (Euclidean Steiner tree).

Pr1 and Pr3 are known to be NP-hard, and I suspect that Problem 2 might be NP-hard for high-genus surfaces. Pr2 has an exact solution for the convex polyhedron case, but it requires an oracle for solving low-degree equations (note that the diameter can be realized by a pair of points that are in the interior of their respective faces). I am not aware of exact solutions to 1 and 3, but they have approximation schemes with $2^{\mathrm{poly}(n)}\cdot \mathrm{poly}\log (1/\epsilon )$ time via brute force structure guess + second-order cone programming (SOCP). Moreover, Pr1 and Pr2 have an FPTAS [Har-Peled99] and Pr3 has an EPTAS.

Given a plane graph $G$, how fast can we find a set of disks whose intersection graph is $G$? By the celebrated Koebe–Andreyev–Thurston Theorem, every planar graph $G$ has a disk-packing representation as a touching graph of nonoverlapping disks, see [Felsner and Rote 2019] for a relatively easy proof through a converging infinite algorithm. In many applications of this theorem, it is not necessary to require adjacent disks to touch; overlapping disks are also fine, see for example [Felsner 2016]. I call this a weak circle representation.

Let $f$ and $g$ be polynomials of degree $d$ each with positive derivative on the whole real line. How many fixed points can the composition $f\circ g$ have?