We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).

In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. This conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler’s conjecture for all n ≥ 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. We also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler’s conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n ≥ 4.

While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).

We study the problem of computing a shortest tour that visits a sequence of k polygons P₁,…,P_k with a total number of n vertices. A tour is an oriented curve such that there exist points p_i ∈ P_i for all i where p_i appears not after p_{i+1}. In a seminal paper, Dror, Efrat, Lubiw and Mitchell (STOC 2003) considered the problem under L₂ distance, and gave Õ(nk) and Õ(nk²) algorithms for disjoint and intersecting convex polygons, respectively. In this paper, we consider the orthogonal setting (with orthogonal polygons and Manhattan distance) and obtain the following results: - a truly subquadratic Õ(n^{2-1/48}) algorithm when consecutive polygons in the sequence are disjoint; - an Õ(n) algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an O(n) algorithm for axis-aligned rectangles; - Õ(n²) and Õ(n^{1.5}k²) algorithms without restrictions. Our algorithms build on a wide range of techniques, including additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles for weighted planar graphs.

We study well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the start configuration to the target configuration while avoiding collisions between the objects and staying within the polygon. Problems of this type have been considered since the early 80s by roboticists and computational geometers. In this paper, we study some of the simplest possible variants where the objects are labeled or unlabeled unit squares or unit disks. In unlabeled reconfiguration, the objects are identical, so that any object is allowed to end at any of the targets positions. In the labeled variant, each object has a designated target position. The results for the labeled variants are direct consequences from our insights on the unlabeled versions. We show that it is PSPACE-hard to decide whether there exists a reconfiguration of (unlabeled/labeled) unit squares even in a simple polygon. Previously, it was only known to be PSPACE-hard in a polygon with holes for both the unlabeled and labeled version [Solovey and Halperin, Int. J. Robotics Res. 2016]. Our proof is based on a result of independent interest, namely that reconfiguration between two satisfying assignments of a formula of Monotone-Planar-3-Sat is also PSPACE-complete. The reduction from reconfiguration of Monotone-Planar-3-Sat to reconfiguration of unit squares extends techniques recently developed to show NP-hardness of packing unit squares in a simple polygon [Abrahamsen and Stade, FOCS 2024]. We also show PSPACE-hardness of reconfiguration of (unlabeled/labeled) unit disks in a polygon with holes. Previously, it was known that unlabeled reconfiguration of disks of two different sizes was PSPACE-hard [Brocken, van der Heijden, Kostitsyna, Lo-Wong and Surtel, FUN 2021].

A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watchman routes that guard the facets of a polytope. We consider the existence of such cycles for a variety of polytopes, the facets of which have a natural combinatorial interpretation. In particular, we prove the following results:

For a set P of n points in general position in the plane, the flip graph F (P ) has a vertex for each noncrossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by one edge flip, i.e., the deletion and addition of exactly one edge. The diameter diam(F (P )) of this flip graph is subject of intensive study. For points P in general position, it is between and 2n - 4, with no improvement for 25 years. For points P in convex position, diam(F (P )) lies between and ≈ 1.95n, where the lower bound was conjectured to be tight up to an additive constant and the upper bound is a very recent breakthrough improvement over several previous bounds of the form 2n - o (n ).

We show that the decision problem of determining whether a given (abstract simplicial) k -complex has a geometric embedding in ℝ d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ { d -1, d } by reducing from pseudoline stretchability. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.

For a set of red and blue points in the plane, a Minimum Bichromatic Spanning Tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in \(O(n\log n)\) time where \( n \) is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a Minimum Plane Bichromatic Spanning Tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al., has a ratio of \(O(\sqrt{n})\) . It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an \(O(\log n)\) -factor approximation algorithm for the general case.

Abstract We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $${\mathbb {R}}^3$$ R 3 . We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$ K 5 , $$K_{5,81}$$ K 5 , 81 , or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$ K 4 , 4 , and $$K_{3,5}$$ K 3 , 5 can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (Isr. J. Math. 46(1–2), 127–144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in $$\Omega (n\log n)$$ Ω ( n log n ) . From the non-realizability of $$K_{5,81}$$ K 5 , 81 , we obtain that any realizable n-vertex graph has $${\mathcal {O}}(n^{9/5})$$ O ( n 9 / 5 ) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

Abstract We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class $${ \forall \exists _{<}\mathbb {R}} $$ ∀ ∃ < R . This implies that the problem is -, -, $$\exists \mathbb {R} $$ ∃ R -, and $$\forall \mathbb {R} $$ ∀ R -hard.

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝ^d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d-1,d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0,1] or a collection of 1 × 1 bins, respectively. If polygons may be rotated, there exist O(1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput., 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O(1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O(1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems. The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x1,…, xn coming online into an oversized array of length γn for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x1,…, xn. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems. As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.

Abstract Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class $$\exists \mathbb {R}$$ ∃ R plays a crucial role in the study of geometric problems. Sometimes $$\exists \mathbb {R}$$ ∃ R is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, $$\exists \mathbb {R}$$ ∃ R deals with existentially quantified real variables. In analogy to $$\Pi _2^p$$ Π 2 p and $$\Sigma _2^p$$ Σ 2 p in the famous polynomial hierarchy, we study the complexity classes $$\forall \exists \mathbb {R}$$ ∀ ∃ R and $$ \exists \forall \mathbb {R}$$ ∃ ∀ R with real variables. Our main interest is the AreaUniversality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AreaUniversality is $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete and support this conjecture by proving $$\exists \mathbb {R}$$ ∃ R - and $$\forall \exists \mathbb {R}$$ ∀ ∃ R -completeness of two variants of AreaUniversality. To this end, we introduce tools to prove $$\forall \exists \mathbb {R}$$ ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class $\forall\exists_<\mathbb{R}$. This implies that the problem is NP-, co-NP-, $\exists\mathbb{R}$- and $\forall\mathbb{R}$-hard.

We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5π}\approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A \leq \frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $\varepsilon>0$ there are sets of squares of total area $\frac{8}{5}+\varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $\left(\frac{1}{2}\right)$, circles in a square $\left(\fracπ{(3+2\sqrt{2})}\approx 0.539\right)$ and circles in a circle $\left(\frac{1}{2}\right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.

Given a neural network, training data, and a threshold, finding weights for the neural network such that the total error is below the threshold is known to be NP-hard. We determine the algorithmic complexity of this fundamental problem precisely, by showing that it is $\exists\mathbb R$-complete. This means that the problem is equivalent, up to polynomial time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, $\exists\mathbb R$ is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP.Neural networks are usually trained using some variation of backpropagation. The result of this paper gives an explanation why techniques commonly used to solve big instances of NP-complete problems (such as SAT solvers, IP solvers, local search, dynamic programming, etc.) seem to be of no use to this task.

We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs, we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex incurs some cost in terms of energy or rotation time that is proportional to the corresponding rotation angle. Our goal is to compute schedules that minimize the following objective functions: (i) in Minimum Makespan Scan Cover (MSC-MS), this is the time until all edges are scanned; (ii) in Minimum Total Energy Scan Cover (MSC-TE), the sum of all rotation angles; (iii) in Minimum Bottleneck Energy Scan Cover (MSC-BE), the maximum total rotation angle at one vertex. Previous theoretical work on MSC-MS revealed a close connection to graph coloring and the cut cover problem, leading to hardness and approximability results. In this paper, we present polynomial-time algorithms for 1D instances of MSC-TE and MSC-BE, but NP-hardness proofs for bipartite 2D instances. For bipartite graphs in 2D, we also give 2-approximation algorithms for both MSC-TE and MSC-BE. Most importantly, we provide a comprehensive study of practical methods for all three problems. We compare three different mixed-integer programming and two constraint programming approaches, and show how to compute provably optimal solutions for geometric instances with up to 300 edges. Additionally, we compare the performance of different meta-heuristics for even larger instances.

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $\Theta(\log \chi (G))$, while for 3D the minimum scan time is not upper bounded by $\chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies P $=$ NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $\nicefrac{3}{2}$, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $k\leq \chi(G)^{c}$. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph.

We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles ("agents") and a particular target region ("tumor") within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by a number of simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising.

The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon and an edge between any two triangulations that differ in exactly one edge. An $r$-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly $r$ times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of $r$-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex $n$-gon, the flip graph of plane trees on an arbitrary set of $n$ points, and the flip graph of noncrossing perfect matchings on a set of $n$ points in convex position. In addition, we consider two flip graphs on classes of nongeometric objects: the flip graph of permutations of $\{1,2,\dots,n\}$ and the flip graph of $k$-element subsets of $\{1,2,\dots,n\}$. In each of the five settings, we prove the existence and nonexistence of rainbow cycles for different values of $r$, $n$, and $k$.