We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure $\mathcal{R}$, and we show that under weak conditions on $\mathcal{R}$, the complexity class $Σ_k \mathcal{R}$ may be characterized in four equivalent ways: (1) by polynomial-time algorithms implemented on $\mathcal{R}$-machines together with witness strings, (2) by the $Σ_k\mathcal{R}$-complete problem $Σ_k\text{SAT}(\mathcal{R})$, (3) by the $k$th existential fragment of second-order metafinite logic over $\mathcal{R}$ via descriptive complexity, and (4) via oracles. By characterizing $Σ_k\mathcal{R}$ in these four ways, we extend previous work and embed it in one coherent framework. In addition, we derive similar results for $\exists_k \mathcal{R}$, the constant-free Boolean part of $Σ_k\mathcal{R}$, by showing that $\exists_k\mathcal{R}$ may be characterized in four analogous ways. Some conditions on $\mathcal{R}$ must be assumed in order to achieve the above quaternity because there are infinite-vocabulary structures for which $\text{NP}(\mathcal{R}) = Σ_1 \mathcal{R}$ does not have a complete problem. Surprisingly, even in these cases, we show that $\text{NP}(\mathcal{R})$ does have a characterization in terms of existential second-order metafinite logic, suggesting that descriptive complexity theory is well suited to working with infinite-vocabulary structures, such as real vector spaces.

Abstract We say that a (multi)graph $$ \user2{G} = (\user2{V},\user2{E}) $$ has geometric thickness t if there exists a straight-line drawing $$ \user2{\varphi }:\user2{V} \to \mathbb{R}^{{\mathbf{2}}} $$ and a t -coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t . This problem was shown to be NP-hard for $$ \user2{t} = \mathbf{2} $$ (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003 ). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is $$\exists \mathbb {R}$$ -complete already for thickness 30 . Moreover, our reduction shows that the problem is $$\exists \mathbb {R}$$ -complete for 4392 -planar graphs, where a graph is k -planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are $$\exists \mathbb {R}$$ -complete.

We devise a data structure that can answer shortest path queries for two query points in a polygonal domain \( P \) on \( n \) vertices. For any \(\varepsilon > 0\) , the space complexity of the data structure is \(O(n^{10+\varepsilon})\) and queries can be answered in \(O(\log n)\) time. Alternatively, we can achieve a space complexity of \(O(n^{9+\varepsilon})\) by relaxing the query time to \(O(\log^{2}n)\) . This is the first improvement upon a conference paper by Chiang and Mitchell [ 15 ] from 1999. They present a data structure with \(O(n^{11})\) space complexity and \(O(\log n)\) query time. Our main result can be extended to include a space-time tradeoff. Specifically, we devise data structures with \(O(n^{9+\varepsilon}/\ell^{4+O(\varepsilon)})\) space complexity and \(O(\ell\log^{2}n)\) query time, for any integer \(1\leq\ell\leq n\) . Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of \( P \) . When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes \(O(n^{6+\varepsilon})\) and the query time \(O(\log^{2}n)\) . When both query points are on the boundary, the space complexity is decreased further to \(O(n^{4+\varepsilon})\) and the query time to \(O(\log n)\) , thereby improving an earlier result of Bae and Okamoto.

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.

We devise a data structure that can answer shortest path queries for two query points in a polygonal domain P on n vertices. For any ε > 0, the space complexity of the data structure is O(n^{10+ε}) and queries can be answered in O(log n) time. Alternatively, we can achieve a space complexity of O(n^{9+ε}) by relaxing the query time to O(log² n). This is the first improvement upon a conference paper by Chiang and Mitchell from 1999. They presented a data structure with O(n^{11}) space complexity and O(log n) query time. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with O(n^{9+ε}/𝓁^{4+O(ε)}) space complexity and O(𝓁 log² n) query time, for any integer 1 ≤ 𝓁 ≤ n. Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of P. When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes O(n^{6+ε}) and the query time O(log²n). When both query points are on the boundary, the space complexity is decreased further to O(n^{4+ε}) and the query time to O(log n), thereby improving an earlier result of Bae and Okamoto.

Abstract Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points $$a,b\in P$$ a , b ∈ P can see each other if the line segment $${\text {seg}} (a,b)$$ seg ( a , b ) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.

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 study algorithmic problems that belong to the complexity class of the existential theory of the reals ([Formula: see text]). A problem is [Formula: see text]-complete if it is as hard as the problem existential theory of the reals (ETR) and if it can be written as an ETR formula. Traditionally, these problems are studied in the real random access machine (RAM), a model of computation that assumes that the storage and comparison of real-valued numbers can be done in constant space and time, with infinite precision. The complexity class [Formula: see text] is often called a real RAM analogue of NP, since the problem ETR can be viewed as the real-valued variant of SAT. The real RAM assumption that we can represent and in which we can compare arbitrary irrational values in constant space and time is not very realistic. Yet this assumption is vital, since some [Formula: see text]-complete problems have an “exponential bit phenomenon,” where there exists an input for the problem, such that the witness of the solution requires geometric coordinates which need exponential word size when represented in binary. The problems that exhibit this phenomenon are NP-hard (since ETR is NP-hard) but it is unknown if they lie in NP. NP membership is often showed by using the famous Cook–Levin theorem, which states that the existence of a polynomial-time verification algorithm for the problem witness is equivalent to NP membership. The exponential bit phenomenon prohibits a straightforward application of the Cook–Levin theorem. In this paper we first present a result which we believe to be of independent interest: we prove a real RAM analogue to the Cook–Levin theorem which shows that [Formula: see text] membership is equivalent to having a verification algorithm that runs in polynomial-time on a real RAM. This gives an easy proof of [Formula: see text]-membership, as verification algorithms on a real RAM are much more versatile than ETR formulas. We use this result to construct a framework to study [Formula: see text]-complete problems under smoothed analysis. We show that for a wide class of [Formula: see text]-complete problems, its witness can be represented with logarithmic input-precision by using smoothed analysis on its real RAM verification algorithm. This shows in a formal way that the boundary between NP and [Formula: see text] (formed by inputs whose solution witness needs high input-precision) consists of contrived input. We apply our framework to well-studied [Formula: see text]-complete recognition problems which have the exponential bit phenomenon such as the recognition of realizable order types or the Steinitz problem in fixed dimension. Interestingly our techniques also generalize to problems with a natural notion of resource augmentation (geometric packing, the art gallery problem).

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.

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.

Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show that our result can be generalized to give an interpolated shape between A and B for any interpolation variable α between 0 and 1, and prove that the resulting morph has a bounded rate of change with respect to α. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.

The Art Gallery Problem (AGP) is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon 풫 and an integer k , the goal is to decide if there exists a set G of k guards within 풫 such that every point p ∈ 풫 is seen by at least one guard g ∈ G . Each guard corresponds to a point in the polygon 풫, and we say that a guard g sees a point p if the line segment pg is contained in 풫. We prove that the AGP is ∃ ℝ-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the AGP, and (2) the AGP is not in the complexity class NP unless NP = ∃ ℝ. As a corollary of our construction, we prove that for any real algebraic number α, there is an instance of the AGP where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set S ⊆ [0, 1] 2 , there exists a polygon with corners at rational coordinates such that for every p ∈ [0, 1] 2 , there is a set of guards of minimum cardinality containing p if and only if p ∈ S . In the ∃ ℝ-hardness proof for the AGP, we introduce a new ∃ ℝ-complete problem ETR-INV. We believe that this problem is of independent interest, as it has already been used to obtain ∃ ℝ-hardness proofs for other problems.

We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.

Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.

A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain$U\subset \mathbb{R}$. We engage in a systematic study to classify CCSPs that are complete of the Existential Theory of the Reals, i.e.,$\exists \mathbb{R}$-complete. To define this class, we first consider the problem ETR, which also stands for Existential Theory of the Reals. In an instance of this problem we are given some sentence of the form$\exists x_{1}, \ldots, x_{n}\in \mathbb{R}$:$\Phi(x_{1},\ldots,\ x_{n})$, where$\Phi$is a well-formed quantifier-free formula consisting of the symbols$\{0,1,\ x_{1},\ldots,\ x_{n},\ +,\ \cdot,\ \geq,\ >, \ \wedge,\ \vee,\ \neg\}$, the goal is to check whether this sentence is true. Now the class$\exists \mathbb{R}$is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP$\subseteq\exists \mathbb{R}\subseteq$PSPACE. We restrict our attention on CCSPs with addition constraints$(x+y=z)$and some other mild technical condition. Previously, it was shown that multiplication constraints$(x\cdot y=z)$, squaring constraints$(x^{2}=y)$, or inversion constraints$(x\cdot y=1)$are sufficient to establish$\exists \mathbb{R}$-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical condition) that have any one well-behaved curved equality constraint$(f(x,\ y)=0)$are$\exists \mathbb{R}$-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint$(f(x,\ y)\geq 0$and$g(x,\ y)\geq 0)$imply$\exists \mathbb{R}$-completeness on the class of such CCSPs. Here, we call a function$f: U^{2}\rightarrow\mathbb{R}$well-behaved if it is a$C^{2}$-function,$f(0,0)=0$, all its partial derivatives$f_{x}, f_{y}, f$are rational in$(0,0), f_{x}(0,0)\neq 0$or$f_{y}(0,0)\neq 0$, and it can be computed on a real RAM. Furthermore we call$f$curved if the curvature of the curve given by$f(x,\ y)=0$is nonzero, at the origin. In this case we call$f$either convexly curved if the curvature is negative, or concavely curved if it is positive. We apply our findings to geometric packing and answer an open question by Abrahamsen et al. [1, FOCS 2020]. Namely, we establish$\exists\mathbb{R}$-completeness of packing convex pieces into a square container under rotations and translations. This work is based on the master's thesis of the second author [2]. The full version of this paper can be found on arXiv [3].

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.

Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.

We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if it can be written as an ETR formula. Traditionally, these problems are studied in the real RAM, a model of computation that assumes that the storage and comparison of real-valued numbers can be done in constant space and time, with infinite precision. The complexity class ER is often called a real RAM analogue of NP, since the problem ETR can be viewed as the real-valued variant of SAT. The real RAM assumption that we can represent and compare irrational values in constant space and time is not very realistic. Yet this assumption is vital, since some ER-complete problems have an “exponential bit phenomenon” where there exists an input for the problem, such that the witness of the solution requires geometric coordinates which need exponential word size when represented in binary. The problems that exhibit this phenomenon are NP-hard (since ETR is NP-hard) but it is unknown if they lie in NP. NP membership is often showed by using the famous Cook-Levin theorem which states that the existence of a polynomial-time verification algorithm for the problem witness is equivalent to NP membership. The exponential bit phenomenon prohibits a straightforward application of the Cook-Levin theorem. In this paper we first present a result which we believe to be of independent interest: we prove a real RAM analogue to the Cook-Levin theorem which shows that ER membership is equivalent to having a verification algorithm that runs in polynomial-time on a real RAM. This gives an easy proof of ER-membership, as verification algorithms on a real RAM are much more versatile than ETR-formulas. We use this result to construct a framework to study ER-complete problems under smoothed analysis. We show that for a wide class of ER-complete problems, its witness can be represented with logarithmic input-precision by using smoothed analysis on its real RAM verification algorithm. This shows in a formal way that the boundary between NP and ER (formed by inputs whose solution witness needs high input-precision) consists of contrived input. We apply our framework to well-studied ER-complete recognition problems which have the exponential bit phenomenon such as the recognition of realizable order types or the Steinitz problem in fixed dimension. Interestingly our techniques also generalize to problems with a natural notion of resource augmentation (geometric packing, the art gallery problem).

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ER-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. A full version of this extended abstract is available on https://arxiv.org/abs/1704.06969.

We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomial-time approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convex set. The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes I follow the same road. They show that, for every graph G of a large-enough class C, the complement of an even subdivision of G belongs to the intersection class I. Then they conclude by invoking the hardness of Maximum Independent Set on the class C, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. '18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks.

Given a simple polygon P on n vertices, two points x , y in P are said to be visible to each other if the line segment between x and y is contained in P . The P oint G uard A rt G allery problem asks for a minimum set S such that every point in P is visible from a point in S . The V ertex G uard A rt G allery problem asks for such a set S subset of the vertices of P . A point in the set S is referred to as a guard. For both variants, we rule out any f ( k ) n o ( k / log k ) algorithm, where k := | S | is the number of guards, for any computable function f , unless the exponential time hypothesis fails. These lower bounds almost match the n O ( k ) algorithms that exist for both problems.

In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k, the goal is to decide if there exists a set G of k guards within P such that every point p ∈ P is seen by at least one guard g∈ G. Each guard corresponds to a point in the polygon P, and we say that a guard g sees a point p if the line segment pg is contained in P.

In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is $$W[1]$$ -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time $$f(k)n^{o(k / \log k)}$$ where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial $$n^{O(k)}$$ -time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.

In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon so that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is a polygon which can be guarded by 3n guards with irrational coordinates but needs 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.

Given a simple polygon $\mathcal{P}$ on $n$ vertices, two points $x,y$ in $\mathcal{P}$ are said to be visible to each other if the line segment between $x$ and $y$ is contained in $\mathcal{P}$. The Point Guard Art Gallery problem asks for a minimum set $S$ such that every point in $\mathcal{P}$ is visible from a point in $S$. The set $S$ is referred to as guards. Assuming integer coordinates and a specific general position assumption, we present the first $O(\log \text{OPT})$-approximation algorithm for the point guard problem for simple polygons. This algorithm combines ideas of a paper of Efrat and Har-Peled [Inf. Process. Lett. 2006] and Deshpande et. al. [WADS 2007]. We also point out a mistake in the latter.

Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n^{ (11+ o(1)) sqrt{n} }, significantly improving the previous best running time of O(2^n n^2) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(sqrt{n}) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers ("cactus graphs"). Based on the above algorithm, we develop a simple and formal framework to count other non-crossing straight-line graphs in n^{O(sqrt{n})} time. We demonstrate the usefulness of the framework by applying it to counting non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3-regular graphs, and more.

Given a simple polygon P on n vertices, two points x,y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The Vertex Guard Art Gallery problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out a f(k)*n^{o(k/log k)} algorithm, for any computable function f, where k := |S| is the number of guards, unless the Exponential Time Hypothesis fails. These lower bounds almost match the n^{O(k)} algorithms that exist for both problems.

Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.

Given a set P of points in the plane we are interested in points that are 'deep' in the set in the sense that they have two opposite quadrants both containing many points of P. We deal with the extremal version of this problem. A pair (a, b) of numbers is admissible if every point set P contains a point p ∈ P that determines a pair (Q,Qop) of opposite quadrants, such that Q contains at least an a-fraction and Qop contains at least a b-fraction of the points of P. We provide a complete description of the set F of all admissible pairs (a, b). This amounts to identifying three line segments and a point on the boundary of F.