Computing a minimum-weight perfect matching for a point set $P$ in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where pairs of points may be added to or removed from the set $P$. Our focus is on maintaining an approximately optimal solution without making too many changes to the solution. More precisely, we are interested in $k$-stable algorithms, which change at most $k$ edges in the matching after each update to the set $P$. In other words, we consider an online setting (with insertions and deletions) with bounded recourse. We study trade-offs between the stability of the algorithm and the approximation ratio of the maintained solution for point sets in $\mathbb{R}^1$. First, we present an $O(\sqrt{n})$-stable algorithm that maintains a $2$-approximation, which we show to be optimal among all algorithms with sublinear stability. Second, we prove that any $o(\log n)$-stable algorithm has unbounded approximation ratio. Our lower bounds hold even in the insertion-only case, while our algorithm works in the fully dynamic case. Moreover, our lower bounds also hold for the bipartite variant of the problem.

We prove that the single-source shortest-path problem on disk graphs can be solved in $O(n\log n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\log^2 n)$ time.

The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√n) nodes whose removal partitions 𝒢 into components of size at most 2n/3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√n) cliques. This result has been generalized to intersection graphs of various other types of disk-like objects. Unfortunately, segment intersection graphs do not admit small clique-based separators, because they can contain arbitrarily large bicliques. This is true even in the simple case of axis-aligned segments. In this paper we therefore introduce biclique-based separators (and, in particular, star-based separators), which are separators consisting of a small number of bicliques (or stars). We prove that any c-oriented set of n segments in the plane, where c is a constant, admits a star-based separator consisting of O(√n) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. We extend our result to intersection graphs of c-oriented polygons. These results immediately lead to an almost-exact distance oracle for such intersection graphs, which has O(n√n) storage and O(√n) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2. This is the first distance oracle for such types of intersection graphs that has subquadratic storage and sublinear query time and that only has an additive error.

We generalize the polynomial-time solvability of $k$-\textsc{Diverse Minimum s-t Cuts} (De Berg et al., ISAAC'23) to a wider class of combinatorial problems whose solution sets have a distributive lattice structure. We identify three structural conditions that, when met by a problem, ensure that a $k$-sized multiset of maximally-diverse solutions -- measured by the sum of pairwise Hamming distances -- can be found in polynomial time. We apply this framework to obtain polynomial time algorithms for finding diverse minimum $s$-$t$ cuts and diverse stable matchings. Moreover, we show that the framework extends to two other natural measures of diversity. Lastly, we present a simpler algorithmic framework for finding a largest set of pairwise disjoint solutions in problems that meet these structural conditions.

Abstract Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of $$\mathbb {R}^2$$ and let $$\mathcal {D}=\{D_1,\ldots,D_n\}$$ be a set of geodesic disks with respect to the metric d. We prove that $$\mathcal {G}^{\times }(\mathcal {D})$$ , the intersection graph of the disks in $$\mathcal {D}$$ , has a clique-based separator consisting of $$O(n^{3/4+\varepsilon })$$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time $$2^{O(n^{3/4+\varepsilon })}$$ , assuming the boundaries of the disks $$D_i$$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $$O(n^{7/4+\varepsilon })$$ storage and can report the hop distance between any two nodes in $$\mathcal {G}^{\times }(\mathcal {D})$$ in $$O(n^{3/4+\varepsilon })$$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.

In One-of-a-Set TSP , also known as the Generalised TSP , the input is a collection P : = { P 1 , . . . , P r } of sets in a metric space and the goal is to compute a minimum-length tour that visits one element from each set. In the Euclidean variant of this problem, each P i is a set of points in R d . Let H i be a hypercube that contains P i , for 1 ⩽ i ⩽ r . We investigate how the complexity of Euclidean One-of-a-Set TSP depends on λ , the ply of the set H : = { H 1 , . . . , H r } of hypercubes. (The ply is the smallest λ such that every point in R d is contained in at most λ of the hypercubes). We show that the problem can be solved in 2 O ( λ 1 / d n 1 − 1 / d ) time, where n : = ∑ i = 1 r | P i | is the total number of points, and that the problem cannot be solved in 2 o ( n ) time when λ = Θ ( n ) , unless the Exponential Time Hypothesis (ETH) fails. In Rectilinear One-of-a-Cube TSP , the input is a set H of hypercubes in R d and the goal is to compute a minimum-length rectilinear tour that visits every hypercube. We show that the problem can be solved in 2 O ( λ 1 / d n 1 − 1 / d log ⁡ n ) time, where n is the number of hypercubes.

Abstract. We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is [Formula: see text]- stable when it makes at most [Formula: see text] changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter [Formula: see text] of the algorithm and the approximation ratio it achieves. We obtain the following results: (i) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Dominating Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 4. (ii) We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by [Formula: see text]. In particular, we give a 1-stable [Formula: see text]-approximation algorithm, a 3-stable [Formula: see text]-approximation algorithm, and an [Formula: see text]-stable [Formula: see text]-approximation algorithm. (iii) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Independent Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 3. (iv) Finally, we present a 2-stable [Formula: see text]-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant [Formula: see text] at all times. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable [Formula: see text]-approximation algorithm.

Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $\mathbb{R}^2$ and let $\mathcal{D}=\{D_1,\ldots,D_n\}$ be a set of geodesic disks with respect to the metric $d$. We prove that $\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in $\mathcal{D}$, has a clique-based separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for $q$-COLORING that runs in time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks $D_i$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.

Let $\mathcal{P}$ be a simple polygon with $m$ vertices and let $P$ be a set of $n$ points inside $\mathcal{P}$. We prove that there exists, for any $\varepsilon>0$, a set $\mathcal{C} \subset P$ of size $O(1/\varepsilon^2)$ such that the following holds: for any query point $q$ inside the polygon $\mathcal{P}$, the geodesic distance from $q$ to its furthest neighbor in $\mathcal{C}$ is at least $1-\varepsilon$ times the geodesic distance to its further neighbor in $P$. Thus the set $\mathcal{C}$ can be used for answering $\varepsilon$-approximate furthest-neighbor queries with a data structure whose storage requirement is independent of the size of $P$. The coreset can be constructed in $O\left(\frac{1}{\varepsilon} \left( n\log(1/\varepsilon) + (n+m)\log(n+m)\right) \right)$ time.

Abstract. Let [Formula: see text] be a set of points in [Formula: see text], where each point [Formula: see text] has an associated transmission range, denoted [Formula: see text]. The range assignment [Formula: see text] induces a directed communication graph [Formula: see text] on [Formula: see text], which contains an edge [Formula: see text] iff [Formula: see text]. In the broadcast range-assignment problem, the goal is to assign the ranges such that [Formula: see text] contains an arborescence rooted at a designated root node and the cost [Formula: see text] of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution—the number of ranges that are modified when a point is inserted into or deleted from [Formula: see text]—and its approximation ratio. To this end we study [Formula: see text]- stable algorithms, which are algorithms that modify the range of at most [Formula: see text] points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm [Formula: see text] that, for any given fixed parameter [Formula: see text], is [Formula: see text]-stable and that maintains a solution with approximation ratio [Formula: see text], where the stability parameter [Formula: see text] only depends on [Formula: see text] and not on the size of [Formula: see text]. We study such trade-offs in three settings. (1) For the problem in [Formula: see text], we present a SAS with [Formula: see text]. Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have [Formula: see text]. We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in [Formula: see text] (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in [Formula: see text], we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in [Formula: see text]. (3) For the problem in [Formula: see text], we also prove that no SAS exists, and we present a [Formula: see text]-stable [Formula: see text]-approximation algorithm. Most results generalize to the setting where, for any given constant [Formula: see text], the range-assignment cost is [Formula: see text].

Finding minimum dominating set and maximum independent set for graphs in the classical online setup are notorious due to their disastrous $Ω(n)$ lower bound of the competitive ratio that even holds for interval graphs, where $n$ is the number of vertices. In this paper, inspired by Newton number, first, we introduce the independent kissing number $ζ$ of a graph. We prove that the well known online greedy algorithm for dominating set achieves optimal competitive ratio $ζ$ for any graph. We show that the same greedy algorithm achieves optimal competitive ratio $ζ$ for online maximum independent set of a class of graphs with independent kissing number $ζ$. For minimum connected dominating set problem, we prove that online greedy algorithm achieves an asymptotic competitive ratio of $2(ζ-1)$, whereas for a family of translated convex objects the lower bound is $\frac{2ζ-1}{3}$. Finally, we study the value of $ζ$ for some specific families of geometric objects: fixed and arbitrary oriented unit hyper-cubes in $I\!\!R^d$, congruent balls in $I\!\!R^3$, fixed oriented unit triangles, fixed and arbitrary oriented regular polygons in $I\!\!R^2$. For each of these families, we also present lower bounds of the minimum connected dominating set problem.

Given a point set P ⊆ X of size n in a metric space (X, dist) of doubling dimension d and two parameters k ∈ ℕ and z ∈ ℕ, the k-center problem with z outliers asks to return a set ${{\mathcal{C}}^ * } = \{ c_1^ * , \cdots ,c_k^ * \} \subseteq X$ of k centers such that the maximum distance of all but z points of P to their nearest center in C* is minimized. An (ε, k, z)-coreset for this problem is a weighted point set P* such that an optimal solution for the k-center problem with z outliers on P* gives a (1 ± ε)-approximation for the k-center problem with z outliers on P. We study the construction of such coresets in the Massively Parallel Computing (MPC) model, and in the insertion-only as well as the fully dynamic streaming model. We obtain the following results, for any given 0d+ z).• In the MPC model the data are distributed over m machines. One is the coordinator machine, which will contain the final answer, the others are worker machines.We present a deterministic 2-round algorithm using $O(\sqrt n )$ machines, where the worker machines have $O(\sqrt {nk/{\varepsilon ^d}} + \sqrt n \cdot \log (z + 1))$ local memory, and the coordinator has $O(\sqrt {nk/{\varepsilon ^d}} + \sqrt n \cdot \log (z + 1) + z)$ local memory. The algorithm can handle point sets P that are distributed arbitrarily (possibly adversarially) over the machines. We also present a randomized algorithm that uses only a single round, under the assumption that the input set P is initially distributed randomly over the machines. Then we present a deterministic algorithm that obtains a trade-off between the number of rounds, R, and the storage per machine.In the streaming model we have a single machine with limited storage, and P is revealed in a streaming fashion.○ We present the first lower bound for the insertion-only streaming model, where the points arrive one by one and no points are deleted. We show that any deterministic algorithm that maintains an (ε, k, z)-coreset must use Ω(k/εd+ z) space. We complement this by a deterministic streaming algorithm using O(k/εd+ z) space, which is thus optimal. ○ For the fully dynamic data streams, where points can be inserted as well as deleted we give a randomized algorithm for point sets from a d-dimensional discrete Euclidean space [Δ]d, where Δ ∈ ℕ indicates the size of the universe from which the coordinates are taken. Our algorithm uses only O((k/εd+ z)log4(kΔ/εδ)) space, and it is the first algorithm for this setting. We also present an Ω((k/εd)logΔ + z) lower bound for deterministic fully dynamic streaming algorithms. ○ For the sliding-window model, we show that any deterministic streaming algorithm that guarantees a (1 + ε)-approximation for the k-center problem with outliers in ℝdmust use Ω((kz/εd) logσ) space, where σ is the ratio of the largest and smallest distance between any two points in the stream. This (negatively) answers a question posed by De Berg, Monemizadeh, and Zhong [1].

Given a connected undirected graph G, a spanning tree is a subgraph T of G such that V(T) = V(G) and T is a tree. A collection of 𝓁 spanning trees T₁,…,T_{𝓁} is {{pairwise k-diverse}} if for every i ≠ j, |E(T_i) △ E(T_j)| ≥ k. Given a connected undirected graph G and integers p, q, k, 𝓁, {Leaf&Internal-Constrained Diverse Spanning Trees} asks whether there are 𝓁 distinct spanning trees T₁,…,T_{𝓁} of G that are {{pairwise k-diverse}} such that each tree has at least p leaves and at least q internal vertices. Similarly, {Leaf&Non-terminal-Constrained Diverse Spanning Trees} takes a connected undirected graph G, V_NT ⊆ V(G), and three integers p, k, 𝓁, and asks if G has 𝓁 spanning trees that are {{pairwise k-diverse}}, and each has at least p leaves and contains the vertices of V_NT as internal. We consider these two problems from the kernelization perspective and provide polynomial kernels for {Leaf&Internal-Constrained Diverse Spanning Trees} and {Leaf&Non-terminal-Constrained Diverse Spanning Trees}, when parameterized by p + q + k + 𝓁 and p + |V_NT| + k + 𝓁, respectively.

Abstract Let F be a set of n objects in the plane and let $$\mathcal {G}^{\times }(F)$$ G × ( F ) be its intersection graph. A balanced clique-based separator of $$\mathcal {G}^{\times }(F)$$ G × ( F ) is a set $$\mathcal {\mathcal {S}}$$ S consisting of cliques whose removal partitions $$\mathcal {G}^{\times }(F)$$ G × ( F ) into components of size at most $$\delta n$$ δ n , for some fixed constant $$\delta <1$$ δ < 1 . The weight of a clique-based separator is defined as $$\sum _{C\in \mathcal {\mathcal {S}}}\log (|C|+1)$$ ∑ C ∈ S log ( | C | + 1 ) . Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then $$\mathcal {G}^{\times }(F)$$ G × ( F ) admits a balanced clique-based separator of weight $$O(\sqrt{n})$$ O ( n ) . We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight $$O(\sqrt{n})$$ O ( n ) , which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ O ( n 2 / 3 log n ) . If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to $$O(\sqrt{n}\log n)$$ O ( n log n ) . (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ O ( n 2 / 3 log n ) . (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight $$O(\sqrt{n}+r\log (n/r))$$ O ( n + r log ( n / r ) )

Abstract Let $$P=\{p_0,\ldots ,p_{n-1}\}$$ P = { p 0 , … , p n - 1 } be a set of points in $${\mathbb R}^d$$ R d , modeling devices in a wireless network. A range assignment assigns a range $$r(p_i)$$ r ( p i ) to each point $$p_i\in P$$ p i ∈ P , thus inducing a directed communication graph $$\mathcal {G}_r$$ G r in which there is a directed edge $$(p_i,p_j)$$ ( p i , p j ) iff $${{\,\textrm{dist}\,}}(p_i, p_j) \leqslant r(p_i)$$ dist ( p i , p j ) ⩽ r ( p i ) , where $${{\,\textrm{dist}\,}}(p_i,p_j)$$ dist ( p i , p j ) denotes the distance between $$p_i$$ p i and $$p_j$$ p j . The range-assignment problem is to assign the transmission ranges such that $$\mathcal {G}_r$$ G r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by $$\sum _{p_i\in P} r(p_i)^{\alpha }$$ ∑ p i ∈ P r ( p i ) α , for some constant $$\alpha >1$$ α > 1 called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points $$p_j$$ p j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away—in our case this means that the transmission ranges will never decrease. The property we want to maintain is that $$\mathcal {G}_r$$ G r has a broadcast tree rooted at the first point

We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ∈C, the number of intersection points between the segments of A and those of B that lie in Δ. We present solutions in the algebraic decision-tree model whose cost is O(n60/31+ε), for any ε>0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal et al. (2021) [3]. A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a “handicap” that turns out to be beneficial for speeding up our algorithm.

Abstract. We study exact algorithms for Metric TSP in [Formula: see text]. In the early 1990s, algorithms with [Formula: see text] running time were presented for the planar case, and some years later an algorithm with [Formula: see text] running time was presented for any [Formula: see text]. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no [Formula: see text] algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time [Formula: see text].

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

A polygon C is an intersecting polygon for a set O of objects in ℝ² if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.

The k-center problem for a point set P asks for a collection of k congruent balls (that is, balls of equal radius) that together cover all the points in P and whose radius is minimized. The k-center problem with outliers is defined similarly, except that z of the points in P do need not to be covered, for a given parameter z. We study the k-center problem with outliers in data streams in the sliding-window model. In this model we are given a possibly infinite stream P = ⟨ p₁,p₂,p₃,…⟩ of points and a time window of length W, and we want to maintain a small sketch of the set P(t) of points currently in the window such that using the sketch we can approximately solve the problem on P(t). We present the first algorithm for the k-center problem with outliers in the sliding-window model. The algorithm works for the case where the points come from a space of bounded doubling dimension and it maintains a set S(t) such that an optimal solution on S(t) gives a (1+ε)-approximate solution on P(t). The algorithm uses O((kz/ε^d)log σ) storage, where d is the doubling dimension of the underlying space and σ is the spread of the points in the stream. Algorithms providing a (1+ε)-approximation were not even known in the setting without outliers or in the insertion-only setting with outliers. We also present a lower bound showing that any algorithm that provides a (1+ε)-approximation must use Ω((kz/ε)log σ) storage.

We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Δ\in C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Δ$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+\varepsilon})$, for any $\varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the \emph{order type} of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.

Let F be a set of n objects in the plane and let G ×(F) be its intersection graph. A balanced clique-based separator of G ×(F) is a set S consisting of cliques whose removal partitions G ×(F) into components of size at most δn, for some fixed constant δ < 1. The weight of a clique-based separator is defined as P C∈S log(|C| + 1). Recently De Berg et al. (SICOMP 2020) proved that if S consists of convex fat objects, then G ×(F) admits a balanced clique-based separator of weight O(√n). We extend this result in several directions, obtaining the following results. Map graphs admit a balanced clique-based separator of weight O(√n), which is tight in the worst case. Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n 2/3 log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(√n log n). Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n 2/3 log n). Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(√n + r log(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for Maximum Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes.

In this paper we study the extraction of representative elements in the data stream model in the form of submodular maximization. Different from the previous work on streaming submodular maximization, we are interested only in the recent data, and study the maximization problem over sliding windows. We provide a general reduction from the sliding window model to the standard streaming model, and thus our approach works for general constraints as long as there is a corresponding streaming algorithm in the standard streaming model. As a consequence, we obtain the first algorithms in the sliding window model for maximizing a monotone/non-monotone submodular function under cardinality and matroid constraints. We also propose several heuristics and show their efficiency in real-world datasets.

Abstract More than 25 years ago, inspired by applications in computer graphics, Chazelle et al. studied the following question: is it possible to cut any set of n lines or other objects in $${\mathbb R}^3$$ R 3 into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an $$O(n^{9/5})$$ O ( n 9 / 5 ) bound on the number of fragments, but only for the very special case of bipartite weavings of lines. Since then only little progress was made, until a breakthrough in 2016 by Aronov and Sharir, who showed that $$O(n^{3/2}{{\,\mathrm{polylog}\,}}n)$$ O ( n 3 / 2 polylog n ) fragments suffice for any set of lines. In a follow-up paper Aronov et al. proved an $$O(n^{3/2+\varepsilon })$$ O ( n 3 / 2 + ε ) bound for triangles, but their method uses high- (albeit constant-) degree algebraic arcs to perform the cuts. Hence, the resulting pieces have curved boundaries. Thus the following natural version of the problem is still wide open: is it possible to cut any collection of n disjoint triangles in $${\mathbb R}^3$$ R 3 into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of n disjoint triangles in $${\mathbb R}^3$$ R 3 into $$O(n^{7/4}{{\,\mathrm{polylog}\,}}n)$$ O ( n 7 / 4 polylog n ) triangular fragments that admit a depth order. The running time of our algorithm is $$O(n^{3.69})$$ O ( n 3.69 ) . We also prove a refined bound that depends on the number, K , of intersections between the projections of the triangle edges onto the xy -plane: we show that $$O(n^{1+\varepsilon } + n^{1/4} K^{3/4}{{\,\mathrm{polylog}\,}}n)$$ O ( n 1 + ε + n

Let V be a set of n points in mathcal R d , called voters . A point p ∈ mathcal R d is a plurality point for V when the following holds: For every q ∈ mathcal R d , the number of voters closer to p than to q is at least the number of voters closer to q than to p . Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q . For most voter sets, a plurality point does not exist. We therefore introduce the concept of β-plurality points , which are defined similarly to regular plurality points, except that the distance of each voter to p (but not to q ) is scaled by a factor β , for some constant 0< β ⩽ 1. We investigate the existence and computation of β -plurality points and obtain the following results. • Define β * d := {β : any finite multiset V in mathcal R d admits a β-plurality point. We prove that β * d = √3/2, and that 1/√ d ⩽ β * d ⩽ √ 3/2 for all d ⩾ 3. • Define β ( p, V ) := sup {β : p is a β -plurality point for V }. Given a voter set V in mathcal R 2 , we provide an algorithm that runs in O ( n log n ) time and computes a point p such that β ( p , V ) ⩾ β * b . Moreover, for d ⩾ 2, we can compute a point p with β ( p , V ) ⩾ 1/√ d in O ( n ) time. • Define β ( V ) := sup { β : V admits a β -plurality point}. We present an algorithm that, given a voter set V in mathcal R d , computes an ((1-ɛ)ċ β ( V ))-plurality point in time O n 2 ɛ 3d-2 ċ log n ɛ d-1 ċ log 2 1ɛ).

We analyze two classic variants of the T RAVELING S ALESMAN P ROBLEM ( TSP ) using the toolkit of fine-grained complexity. Our first set of results is motivated by the B ITONIC TSP problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in O ( n 2 ) time. While the near-quadratic dependency of similar dynamic programs for L ONGEST C OMMON S UBSEQUENCE and D ISCRETE F réchet D istance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic TSP in O ( n log 2 n ) time and its bottleneck version in O ( n log 3 n ) time. In the more general pyramidal TSP problem, the points to be visited are labeled 1,… , n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) TSP problem also work for the pyramidal TSP problem in the plane. Our second set of results concerns the popular k - OPT heuristic for TSP in the graph setting. More precisely, we study the k - OPT decision problem, which asks whether a given tour can be improved by a k - OPT move that replaces k edges in the tour by k new edges. A simple algorithm solves k - OPT in O ( n k ) time for fixed k . For 2- OPT , this is easily seen to be optimal. For k =3, we prove that an algorithm with a runtime of the form Õ( n 3−ɛ ) exists if and only if A LL -P AIRS S HORTEST P ATHS in weighted digraphs has such an algorithm. For general k - OPT , it is known that a runtime of f ( k ) · n o ( k / log k ) would contradict the Exponential Time Hypothesis. The results for k =2,3 may suggest that the actual time complexity of k - OPT is Θ ( n k ). We show that this is not the case, by presenting an algorithm that finds the best k -move in O ( n ⌊ 2 k /3 ⌋+1 ) time for fixed k ≥ 3. This implies that 4- OPT can be solved in O ( n 3 ) time, matching the best-known algorithm for 3- OPT . Finally, we show how to beat the quadratic barrier for k =2 in two important settings, namely, for points in the plane and when we want to solve 2- OPT repeatedly.

We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results. - For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).

Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).

Let P = {p₀,…,p_{n-1}} be a set of points in ℝ^d, modeling devices in a wireless network. A range assignment assigns a range r(p_i) to each point p_i ∈ P, thus inducing a directed communication graph 𝒢_r in which there is a directed edge (p_i,p_j) iff dist(p_i, p_j) ⩽ r(p_i), where dist(p_i,p_j) denotes the distance between p_i and p_j. The range-assignment problem is to assign the transmission ranges such that 𝒢_r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by ∑_{p_i ∈ P} r(p_i)^α, for some constant α > 1 called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points p_j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away - in our case this means that the transmission ranges will never decrease. The property we want to maintain is that 𝒢_r has a broadcast tree rooted at the first point p₀. Our results include the following. - We prove that already in ℝ¹, a 1-competitive algorithm does not exist. In particular, for distance-power gradient α = 2 any online algorithm has competitive ratio at least 1.57. - For points in ℝ¹ and ℝ², we analyze two natural strategies for updating the range assignment upon the arrival of a new point p_j. The strategies do not change the assignment if p_j is already within range of an existing point, otherwise they increase the range of a single point, as follows: Nearest-Neighbor (NN) increases the range of NN(p_j), the nearest neighbor of p_j, to dist(p_j, NN(p_j)), and Cheapest Increase (CI) increases the range of the point p_i for which the resulting cost increase to be able to reach the new point p_j is minimal. We give lower and upper bounds on the competitive ratio of these strategies as a function of the distance-power gradient α. We also analyze the following variant of NN in ℝ² for α = 2: 2-Nearest-Neighbor (2-NN) increases the range of NN(p_j) to 2⋅ dist(p_j,NN(p_j)), - We generalize the problem to points in arbitrary metric spaces, where we present an O(log n)-competitive algorithm.

Abstract It is well known that any set of n intervals in $$\mathbb {R} ^1$$ R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.

We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d\ge 2$ for many well-known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into $d$-dimensional grids, and it allows us to derive matching $2^{\Omega(n^{1-1/d})}$ lower bounds under the exponential time hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.

Let $V$ be a multiset of $n$ points in $\mathbb{R}^d$, which we call voters, and let $k\geq 1$ and $\ell\geq 1$ be two given constants. We consider the following game, where two players $\mathcal{P}$ and $\mathcal{Q}$ compete over the voters in $V$: First, player $\mathcal{P}$ selects $k$ points in $\mathbb{R}^d$, and then player $\mathcal{Q}$ selects $\ell$ points in $\mathbb{R}^d$. Player $\mathcal{P}$ wins a voter $v\in V$ iff $\mathrm{dist}(v,P) \leq \mathrm{dist}(v,Q)$, where $\mathrm{dist}(v,P) := \min_{p\in P} \mathrm{dist}(v,p)$ and $\mathrm{dist}(v,Q)$ is defined similarly. Player $\mathcal{P}$ wins the game if he wins at least half the voters. The algorithmic problem we study is the following: given $V$, $k$, and $\ell$, how efficiently can we decide if player $\mathcal{P}$ has a winning strategy, that is, if $\mathcal{P}$ can select his $k$ points such that he wins the game no matter where $\mathcal{Q}$ places her points. Banik et al. devised a singly-exponential algorithm for the game in $\mathbb{R}^1$, for the case $k=\ell$. We improve their result by presenting the first polynomial-time algorithm for the game in $\mathbb{R}^1$. Our algorithm can handle arbitrary values of $k$ and $\ell$. We also show that if $d\geq 2$, deciding if player $\mathcal{P}$ has a winning strategy is $Σ_2^P$-hard when $k$ and $\ell$ are part of the input. Finally, we prove that for any dimension $d$, the problem is contained in the complexity class $\exists\forall \mathbb{R}$, and we give an algorithm that works in polynomial time for fixed $k$ and $\ell$.

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $$s\in P$$ be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, s must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width w. We describe several algorithms for both the regular and the hop-bounded versions, and show that both problems are solvable in polynomial time in strips of small constant width. These results complement the hardness results in a companion paper (de Berg et al. in Algorithmica, 2017).

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $$s\in P$$ be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem—in the latter s must be able to reach every node within a specified number of hops—where we also consider how the complexity depends on the width w of the strip. We prove the following two lower bounds. First, we show that the regular version of the problem is $${\mathsf {W[1]}}$$ -complete when parameterized by the solution size k. More precisely, we show that the problem does not admit an algorithm with running time $$f(k)n^{o(\sqrt{k})}$$ , unless ETH fails. The construction can also be used to show an $$f(w)n^{\varOmega (w)}$$ lower bound when we parameterize by the strip width w. Second, we prove that the hop-bounded version of the problem is NP-hard in strips of width 40. These results complement the algorithmic results in a companion paper (de Berg et al. in Algorithmica, submitted).

Let $S$ be a set of $n$ points on a polyhedral terrain $\mathcal{T}$ in $\mathbb{R}^3$, and let $\varepsilon>0$ be a fixed constant. We prove that $S$ admits a $(2+\varepsilon)$-spanner with $O(n\log n)$ edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of $n$ weighted points in $\mathbb{R}^d$ admits an additively weighted $(2+\varepsilon)$-spanner with $O(n)$ edges; this improves the previously best known bound on the spanning ratio (which was $5+\varepsilon$) and almost matches the lower bound.

We study exact algorithms for Euclidean TSP in Rd. In the early 1990s algorithms with nO(√n)running time were presented for the planar case, and some years later an algorithm with nO(n1-1/d)running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2O(n1-1/d-ε) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2O(n1-1/d)algorithm and by showing that a 2o(n1-1/d)algorithm does not exist unless ETH fails.

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2O(n1−1/d) for any fixed dimension d≥ 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques.

We study the following problem: preprocess a set $$\mathcal {O}$$ of objects into a data structure that allows us to efficiently report all pairs of objects from $$\mathcal {O}$$ that intersect inside an axis-aligned query range $${Q}$$ . We present data structures of size $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ and with query time $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ time, where k is the number of reported pairs, for two classes of objects in $${\mathbb R}^2$$ : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in $${\mathbb R}^3$$ , we present a data structure of size $$O(n\sqrt{n}\cdot {{\mathrm{polylog\,}}}n)$$ and query time $$O((\sqrt{n}+k)\cdot {{\mathrm{polylog\,}}}n)$$ . When the objects and query are fat, we obtain $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ query time using $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ storage.

Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfiguring one independent set into another, using two different processes: (1) exchanging exactly k vertices in each step, or (2) removing or adding one vertex in each step while ensuring the intermediate sets contain at most k fewer vertices than the initial solution. We are interested in determining the minimum value of k for which this reconfiguration is possible, and bound these threshold values in terms of several structural graph parameters. For hereditary graph classes we identify structures that cause the reconfiguration threshold to be large.

Let V be a set of n points in R d , which we call voters. A point p ∈ R d is preferred over another point p ′ ∈ R d by a voter υ ∈ V if dist(υ, p ) < dist(υ, p ′). A point p is called a plurality point if it is preferred by at least as many voters as any other point p ′. We present an algorithm that decides in O ( n log n ) time whether V admits a plurality point in the L 2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L 1 norm, where each point υ ∈ V has a preference vector 〈 w 1 (υ),…, w d (υ)〉 and the distance from υ to any point p ∈ R d is given by ∑ i =1 d w i (υ)· | x i (υ)− x i ( p )|. For this case we can compute in O ( n d −1 ) time the set of all plurality points of V . When all preference vectors are equal, the running time improves to O ( n ).

Let T be a terrain, and let P be a set of points (locations) on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index of a point p on P, that is, the number of points in P that are visible from p. The total visibility-index problem asks for computing the visibility index of every point in P. Most applications of this problem involve 2-dimensional terrains represented by a grid of n × n square cells, where each cell is associated with an elevation value, and P consists of the center-points of these cells. Current approaches for computing the total visibility-index on such a terrain take at least quadratic time with respect to the number of the terrain cells. While finding a subquadratic solution to this 2D total visibility-index problem is an open problem, surprisingly, no subquadratic solution has been proposed for the one-dimensional (1D) version of the problem; in the 1D problem, the terrain is an x-monotone polyline, and P is the set of the polyline vertices. We present an O(n log2 n) algorithm that solves the 1D total visibility-index problem in the RAM model. Our algorithm is based on a geometric dualization technique, which reduces the problem into a set of instances of the red-blue line segment intersection counting problem. We also present a parallel version of this algorithm, which requires O(log2 n) time and O(n log2 n) work in the CREW PRAM model. We implement a naive O(n2) approach and three variations of our algorithm: one employing an existing red-blue line segment intersection algorithm and two new approaches that perform the intersection counting by leveraging features specific to our problem. We present experimental results for both serial and parallel implementations on large synthetic and real-world datasets, using two distinct hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude on large datasets. Furthermore, we show that our new intersection counting implementations achieve more than 8 times speedup over the existing red-blue line segment intersection algorithm. Our parallel implementation is able to process a terrain of 224 vertices in under 1 minute using 16 cores, achieving more than 7 times speedup over serial execution.

Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) is minimized, where CH(P_i) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n^2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time.

In a geometric k-clustering problem the goal is to partition a set of points in R^d into k subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set S: given a query box Q and an integer k > 2, compute an optimal k-clustering for the subset of S inside Q. We obtain the following results. * We present a general method to compute a (1+epsilon)-approximation to a range-clustering query, where epsilon>0 is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric and a variant of k-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. * We extend our method to deal with capacitated k-clustering problems, where each of the clusters should not contain more than a given number of points. * For the special cases of rectilinear k-center clustering in R^1, and in R^2 for k = 2 or 3, we present data structures that answer range-clustering queries exactly.

More than 25 years ago, inspired by applications in computer graphics, Chazelle et al. (FOCS 1991) studied the following question: Is it possible to cut any set of n lines or other objects in R3into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an O(n9/4) bound on the number of fragments, but only for the very special case of bipartite weavings of lines. Since then only little progress was made, until a recent breakthrough by Aronov and Sharir (STOC 2016) who showed that O(n3/2polylog n) fragments suffice for any set of lines. In a follow-up paper Aronov, Miller and Sharir (SODA 2017) proved an O(n3/2+ε) bound for triangles, but their method uses high-degree algebraic arcs to perform the cuts. Hence, the resulting pieces have curved boundaries. Moreover, their method uses polynomial partitions, for which currently no algorithm is known. Thus the most natural version of the problem is still wide open: Is it possible to cut any collection of n disjoint triangles in R3 into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of n disjoint triangles in R3 into O(n7/4polylog n) triangular fragments that admit a depth order. The running time of our algorithm is O(n3.69). We also prove a refined bound that depends on the number, K, of intersections between the projections of the triangle edges onto the xy-plane: we show that O(n1+ε+ n1/4K3/4polylog n) fragments suffice to obtain a depth order. This result extends to xy-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs in general position, constituting the first subquadratic bound for surface patches. Finally, as a byproduct of our approach we obtain a faster algorithm to cut a set of lines into O(n3/2polylog n) fragments that admit a depth order. Our algorithm for lines runs in O(n5.38) time, while the previous algorithm uses O(n8.77) time.

Let S be a set of n polygonal trajectories in the plane and k be a fixed constant. We present a data structure to store S so that, given a k-vertex query trajectory Q, we can answer the following queries approximately:

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. - First we consider CF-colorings of a set S of unit squares with respect to points. Our method maintains a CF-coloring that uses O(log n) colors at any time, where n is the current number of squares in S, at the cost of only O(log n) recolorings per insertion or deletion We generalize the method to rectangles whose sides have lengths in the range [1, c], where c is a fixed constant. Here the number of used colors becomes O(log^2 n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O(log^2 N log^2 n) colors. The number of recolorings for both methods stays in O(log n). - We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with O(log^3 n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O(log n) recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with O(sqrt(n) log^2 n) colors for points with respect to rectangles, at the cost of O(log n) recolorings per insertion and O(1) recolorings per deletion. These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.

We present a new algorithm for the widely used density-based clustering method DBScan. Our algorithm computes the DBScan-clustering in O(n log n) time in R^2, irrespective of the scale parameter \eps, but assuming the second parameter MinPts is set to a fixed constant, as is the case in practice. We also present an O(n log n) randomized algorithm for HDBScan in the plane---HDBScans is a hierarchical version of DBScan introduced recently---and we show how to compute an approximate version of HDBScan in near-linear time in any fixed dimension.

We introduce the dynamic conflict-free coloring problem for a set S of intervals in R 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings; - a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.

We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.

Let S be a set S of n points on a polyhedral terrain T in ℝ3, and let ∊ > 0 be a fixed constant. We prove that S admits a (2 + ∊)-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in ℝd admits an additively weighted (2 + ∊)-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ∊), and almost matches the lower bound.

Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. Our first set of results is motivated by the Bitonic TSP problem: given a set of $n$ points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in $O(n^2)$ time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Frechet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic TSP in $O(n \log^2 n)$ time and its bottleneck version in $O(n \log^3 n)$ time. Our second set of results concerns the popular $k$-OPT heuristic for TSP in the graph setting. More precisely, we study the $k$-OPT decision problem, which asks whether a given tour can be improved by a $k$-OPT move that replaces $k$ edges in the tour by $k$ new edges. A simple algorithm solves $k$-OPT in $O(n^k)$ time for fixed $k$. For 2-OPT, this is easily seen to be optimal. For $k=3$ we prove that an algorithm with a runtime of the form $\tilde{O}(n^{3-ε})$ exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. The results for $k=2,3$ may suggest that the actual time complexity of $k$-OPT is $Θ(n^k)$. We show that this is not the case, by presenting an algorithm that finds the best $k$-move in $O(n^{\lfloor 2k/3 \rfloor + 1})$ time for fixed $k \geq 3$. This implies that 4-OPT can be solved in $O(n^3)$ time, matching the best-known algorithm for 3-OPT. Finally, we show how to beat the quadratic barrier for $k=2$ in two important settings, namely for points in the plane and when we want to solve 2-OPT repeatedly.

In many scientific fields, it is common to encounter raster data sets consisting of categorical data, such as soil type or land usage of a terrain. A problem that arises in the presence of such data is the following: given a raster G of n cells storing categorical data, compute for every cell c in G the number of different categories appearing within a window centered at c. The window can either be a (2r+1)x(2r+1) square or a disk of radius r for a positive integer parameter r. We call this the categorical richness problem, and we present two algorithms for it: one for square windows that runs in O(n) time and one for circular windows that runs in O((1+K/r)n) time, where K is the number of distinct categories in G. The algorithms are not only efficient in theory, but also in practice: our experiments show that our algorithms can handle raster data of hundreds of millions of cells.

We consider the following motion-planning problem: we are given \mbim unit discs in a simple polygon with \mbin vertices, each at their own start position, and we want to move the discs to a given set of \mbim target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in \mbiO(m2+mn) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.

Progressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We present a framework for analyzing such algorithms, and develop efficient progressive algorithms for two geometric problems: computing the convex hull of a planar point set, and finding popular places in a set of trajectories.

We show that, for any $\gamma > 0$, the combinatorial complexity of the union of $n$ locally $\gamma$-fat objects of constant complexity in the plane is $\frac{n}{\gamma^4} 2^{O(\log^*n)}$. For the special case of $\gamma$-fat triangles, the bound improves to $O(n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}})$.

We study two versions of the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound d_{max} on the maximum displacement of any point within one time step. We show how to maintain the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+ε)-approximation of the optimal 2-center. In many cases---namely when the distance between the centers of the disks is relatively large or relatively small---the solution we maintain is actually optimal.

This special issue contains a selection of papers from the 18th European Symposium on Algorithms (ESA), which was held September 6-8, 2010 in Liverpool (UK).The European Symposium on Algorithms is one of the premier algorithms conferences worldwide, featuring high-quality papers on efficient algorithms and data structures in computer science, discrete applied mathematics, and operations research.ESA publishes both theory-oriented papers (in the Design and Analysis Track) and experimentation-oriented papers (in the Engineering and Application Track).For this special issue seven excellent papers were selected from the Design and Analysis Track.All papers went through the thorough reviewing process that is standard for papers published in Algorithmica.Bansal, Gupta, Li, Mestre, Nagarajan and Rudra study matchings in random graphs in their paper When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.They consider a model where each edge exists with a certain probability and the algorithm can query edges for their existence; when the edge exists, the algorithm must use it in the matching.Using clever LP rounding schemes, they obtain several results that improve and/or generalize many of the existing solutions for stochastic matchings.The sporadic task model is a model of recurrent processes in real-time systems that has received great attention in the last years.The paper Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems by Bonifaci and Marchetti-Spaccamela solves a fundamental open problem in the sporadic task model, namely to decide if a system of sporadic tasks is feasible.They also solve two other important problems in the area, concerning online feasibility and concerning schedulability.

The skeleton of a polyhedral set is the union of its edges and vertices. Let $\mathcal {P}$ be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in $\mathcal {P}$ . We prove that the total length of the skeleton of the union of the polytopes in $\mathcal {P}$ is at most O(α(n)⋅log∗ n⋅logf max) times the sum of the skeleton lengths of the individual polytopes.

Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algorithm for the problem of finding a partition with minimum stabbing number. It is based on an algorithm that finds an optimal partition for histograms. We also study Steiner triangulations of a simple (non-rectilinear) polygon P. Here the stabbing number is defined as the maximum number of triangles that can be stabbed by any line segment inside P. We give an O(1)-approximation algorithm for the problem of computing a Steiner triangulation with minimum stabbing number.

Over the past decade, the kinetic-data-structures framework has become the standard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional time-slicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum displacement of any point in one time step. We study the maintenance of the convex hull and the Delaunay triangulation of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any point p ∑ P the disk of radius dmax contains at most k points. We analyze our algorithms in terms of ∑k , the so-called k-spread of P. We show how to update the convex hull at each time step in O(k∑k log2 n) amortized time. For the Delaunay triangulation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2 ∑k2) at each time step.

An imprecise region, also called a vernacular region, is a region without a precise or administrative boundary. We present a new method to delineate imprecise regions from a set of points that are likely to lie inside the region. We use shortest-path graphs based on the squared Euclidean distance which capture the shape of region boundaries well. Shortest-path graphs naturally adapt to point sets of varying density, and they are always connected. As opposed to neighborhood graphs, they use a non-local criterion to determine which points to connect. Furthermore, shortest-path graphs can easily be extended to take geographic context into account by modeling context as "soft" obstacles. We present efficient algorithms to compute shortest-path graphs with or without geographic context. We experimentally evaluate the quality of the imprecise regions computed with our method. To fairly compare our results to those obtained by the common KDE approach, we also show how to integrate context into KDE by again using soft obstacles.

The natural way of modeling water flow on a triangulated terrain is to make the fundamental assumption that water follows the direction of steepest descent (dsd). However, computing watersheds and other flow-related structures according to the dsd model in an exact manner is difficult: the dsd model implies that water does not necessarily follow terrain edges, which makes designing exact algorithms difficult and causes robustness problems when implementing them. As a result, existing software implementations for computing watersheds are inexact: they either assume a simplified flow model or they perform computations using inexact arithmetic, which leads to inexact and sometimes inconsistent results. We perform a detailed study of various issues concerning the exact or approximate computation of watersheds according to the dsd model. Our main contributions are the following.

Flow-related structures on terrains are defined in terms of paths of steepest descent (or ascent). A steepest descent path on a polyhedral terrain T with n vertices can have Θ(n2) complexity. The watershed of a point p—the set of points on T whose paths of steepest descent reach p—can have complexity Θ(n3). We present a technique for tracing a collection of n paths of steepest descent on T implicitly in O(n log n) time. We then derive O(n log n) time algorithms for: (i) computing for each local minimum p of T the triangles contained in the watershed of p and (ii) computing the surface network graph of T. We also present an O(n2) time algorithm that computes the watershed area for each local minimum of T.

Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function: $$\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\mbox{ if $p=q$,}\\ \operatorname {w}(p)+\mathbf{d}(p,q)+ \operatorname {w}(q)&\mbox{ if $p\neq q$.}\end{array}\right.$$ We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d ω -metric. For any given ε>0, we can apply our method to obtain (5+ε)-spanners with a linear number of edges for three cases: points in Euclidean space ℝ d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝ d where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)-spanners for weighted point points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlog n). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2−ε.

We present a new (1+ε)-spanner for sets of n points in ℝ d . Our spanner has size O(n/ε d−1) and maximum degree O(log d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n 2/ε d−1), and using a supporting data structure of size O(nlog d n), we can handle events in time O(log d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ d whose performance does not depend on the spread of the point set.

We prove that the union complexity of a set of n constant-complexity locally fat objects (which can be curved and/or non-convex) in the plane is O(λt+2(n) log n), where t is the maximum number of times the boundaries of any two objects intersect. This improves the previously best known bound by a logarithmic factor.

Suppose we want to move a passive object along a given path, among obstacles in the plane, by pushing it with an active robot. We present two algorithms to compute a push plan for the case that the object and robot are disks and the obstacles are non-intersecting line segments. The first algorithm assumes that the robot must maintain contact with the object at all times, and produces a shortest path. There are also situations, however, where the robot has no choice but to let go of the object occasionally. Our second algorithm handles such cases, but no longer guarantees that the produced path is the shortest possible.

Let $P$ be a set of points in $\Reals^d$, and let $\alpha \ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^{\alpha}$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by \tsp($d,\alpha$). We design a 5-approximation algorithm for \tsp(2,2) and generalize this result to obtain an approximation factor of $3^{\alpha-1}+\sqrt{6}^{\,\alpha}\!/3$ for $d=2$ and all $\alpha\ge2$. We also study the variant Rev-\tsp\ of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-\tsp$(2,\alpha)$ with $\alpha\ge2$, and we show that Rev-\tsp$(d, \alpha)$ is \apx-hard if $d\ge3$ and $\alpha>1$. The \apx-hardness proof carries over to \tsp$(d, \alpha)$ for the same parameter ranges.

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p 0,p 1,p 2,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k 2) additional storage.

We present a new (1+ε)-spanner for sets of n points in Rd. Our spanner has size O(n/εd-1) and maximum degree O(logd n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n2/εd-1), and using a supporting data structure of size O(n logdn) we can handle events in time O(logd+1n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in Rd whose performance does not depend on the spread of the point set.

We study the complexity of the visibility map of terrains whose triangles are fat, not too steep and have roughly the same size. It is known that the complexity of the visibility map of such a terrain with n triangles is θ(n2) in the worst case. We prove that if the elevations of the vertices of the terrain are subject to uniform noise which is proportional to the edge lengths, then the worst-case expected (smoothed) complexity is only θ(n). This provides an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.

No abstract available.

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are: If the objects are 3-dimensional balls that roll on a plane, then we can detect collisions with a KDS of size O ( n log n ) that can handle events in O (log 2 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects are convex fat 3-dimensional objects of constant complexity that are free-flying in ℝ 3 , then we can detect collisions with a KDS of O ( n log 6 n ) size that can handle events in O (log 7 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects have similar sizes then the size of the KDS becomes O ( n ) and events can be handled in O (log n ) time.

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of n points in $\mathbb{R}^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports orthogonal range queries in $O(n^{1-1/d}+k)$ time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the kinetic data structure (KDS) processes $O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in $O(\log n)$ time, and each point is involved in $O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees, for sets of points in $\mathbb{R}^2$. Rank-based longest-side kd-trees can be kinetized efficiently as well, and like longest-side kd-trees, they support $\varepsilon$-approximate nearest-neighbor, $\varepsilon$-approximate farthest-neighbor, and $\varepsilon$-approximate range queries with convex ranges in $O((1/\epsilon)\log^2n)$ time. The KDS processes $O(n^3\log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in $O(\log^2n)$ time, and each point is involved in $O(\log n)$ certificates.

We present a new and simple (1+ε)-spanner of size O(nε2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/ε2).λs+2(n)), and at each event the spanner can be updated in O(1) time.

We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally γ-fat objects. We prove that the union complexity of any set of n such objects is O(λ s+2(n)log 2 n). This improves the best known bound, and extends it to a more general class of objects.

We present new results for three problems dealing with a set $\mathcal{P}$ of n convex constant-complexity fat polyhedra in 3-space. (i) We describe a data structure for vertical ray shooting in $\mathcal{P}$ that has $O(\log^2 n)$ query time and uses $O(n\log^2 n)$ storage. (ii) We give an algorithm to compute in $O(n\log^3 n)$ time a depth order on $\mathcal{P}$ if it exists. (iii) We give an algorithm to verify in $O(n\log^3 n)$ time whether a given order on $\mathcal{P}$ is a valid depth order. All three results improve on previous results.

We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O (( N / B ) 1−1/ d + T / B ) I/Os, where N is the number of d -dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all N / B leaves in the tree even when T = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similarly to the best-known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.

We study the following variant of the well-known line-simpli-ficationproblem: we are getting a possibly infinite sequence of points p0,p1,p2,... in the plane defining a polygonal path, and as wereceive the points we wish to maintain a simplification of the pathseen so far. We study this problem in a streaming setting, where weonly have a limited amount of storage so that we cannot store all thepoints. We analyze the competitive ratio of our algorithms, allowingresource augmentation: we let our algorithm maintain a simplificationwith 2k (internal) points, and compare the error of oursimplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio forthree cases: convex paths where the error is measured using theHausdorff distance (or Frechet distance), xy-monotone paths where the error is measured using theHausdorff distance (or Frechet distance), and general paths where the error is measured using theFrechet distance. In the first case the algorithm needs O(k) additionalstorage, and in the latter two cases the algorithm needs O(k2) additional storage.

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in Rd. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search queries in O(n1−1/d+ k) time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes O(n2) events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in O(logn) time, and each point is involved in O(1) certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in R2. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in O((1/ε) log2 n) time. The KDS processes O(n3 logn) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log2 n) time, and each point is involved in O(logn) certificates. Background. Due to the increased availability of GPS systems and to other technological advances, motion data is becoming more and more available in a variety of application areas: air-traffic control,

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2+ε) storage and preprocessing time, and queries can be answered in O(log2 n) time. A trade-off between storage and query time is also possible: for any m with n < m < n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that queries take O((n/√m)log2 n) time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with n < m < n3, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m1/3)log n+k) time, where k is the number of answers.

A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable, for example, population. We present an algorithm for constructing rectilinear cartograms (each region is represented by a rectilinear polygon) with zero cartographic error and correct region adjacencies, and we test our algorithm on various data sets. It produces regions of very small complexity---in fact, most regions are rectangles---while still ensuring both exact areas and correct adjacencies for all regions.Our algorithm uses a novel subroutine that is interesting in its own right, namely a polynomial-time algorithm for computing optimal binary space partitions (BSPs) for rectilinear maps. This algorithm works for a general class of optimality criteria, including size and depth. We use this generality in our application to computing cartograms, where we apply a dedicated cost function leading to BSP's amenable to the constructing of high-quality cartograms.

Let S be a set of n points moving on the real line. The kinetic sorting problem is to maintain a data structure on the set S that makes it possible to quickly generate a sorted list of the points in S, at any given time. We prove tight lower bounds for this problem, which show the following: with a subquadratic maintenance cost one cannot obtain any significant speed-up on the time needed to generate the sorted list (compared to the trivial O(n log n) time), even for linear motions.We also describe a kinetic data structure for so-called gift-wrapping queries on a set S of n moving points in the plane: given a point q and a line l through q such that all points from S lie on the same side of l, report which point pi ∈ S is hit first when l is rotated around q. Our KDS allows a trade-off between the query time and the maintenance cost: for any Q with 1 ≤ Q ≤ n, we can achieve O(Q log n) query time with a KDS that processes O(n2+ε/Q1+1/δ) events, where δ is the maximum degree of the polynomials describing the motions of the points. This allows us to reconstruct the convex hull quickly when the number of points on the convex hull is small. The structure also allows us to answer extreme-point queries (given a query direction ⃗d, what is the point from S that is extreme in direction ⃗d?) and convex-hull containment queries (given a query point q, is q inside the current convex hull?).

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in B or more rectangles in S, the structure answers a rectangle query using O(√N/B + T/B) memory transfers and a point query using O((N/B)ε) memory transfers for any ε > 0, where B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.

We describe a data structure for vertical ray shooting in a set of n convex fat polyhedra of constant complexity in 3-space. The structure has O(log2 n) query time, and it uses O(n log3 n(log log n)2) storage. It can also be used for fat objects with curved boundaries, at the cost of a small increase in storage.

We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B)1 1/d + T/B) I/Os, where N is the number of d-dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all N/B leaves in the tree even when T = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similar to the best known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.

In this paper, we study two recent theoretical models--a population-sizing model and a convergence model--and examine their assumptions to gain insights into the conditions under which selecto-recombinative GAs work well. We use these insights to formulate several design rules to develop competent GAs for practical problems. To test the usefulness of the design rules, we consider as a case study the map-labeling problem, an NP-hard problem from cartography. We compare the predictions of the theoretical models with the actual performance of the GA for the map-labeling problem. Experiments show that the predictions match the observed scale-up behavior of the GA, thereby strengthening our claim that the design rules can guide the design of competent selecto-recombinative GAs for realistic problems.

A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. We describe a new algorithm to construct a box-tree for objects in a 3D scene, and we analyze its worst-case query time for approximate range queries. If the input scene has certain characteristics that we derived from our application---collision detection in industrial installations---then the query times are polylogarithmic, not only for searching with boxes but also for range searching with other constant-complexity ranges.

A box-tree is a \ifasci so-called \emph{bounding-volume hierarchy} \else bounding-volume hierarchy \fi that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.

We present anew technique to maintain a BSP for a set of n moving disj oint segments in the plane. Our kinetic BSP uses O(n log n) storage and it undergoes O(n 2 ) changes in the worst case, assuming that the endpoints of the segments move along bounded-degree algebraically dened trajecto- ries. The response time (the time needed to update the BSP when it undergoes a change) is O(log 2 n). A random- ized variant achieves O(log n) expected response time, while the worst-case response time remains O(log 2 n).

We study the problem of computing schematized versions of network maps , like railroad maps. Every path of the schematized map has two or three links with restricted orientations, and topologically, the schematized map must be equivalent to the input map. Our approach applies to several types of schematizations, and certain additional constraints can be added. In the general case our algorithm takes $O(n\log^3n)$ time, and when all paths in the input are monotone in some (not necessarily the same) direction, it runs in $O(n\log n)$ time.

IntroductionWe revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations.Under very general computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane.Such lower bounds-the first to be obtained in the kinetic context-are necessary to evaluate the efliciency of kinetic data structures when the attribute to be maintained is not canonically defined.

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers.We obtain the following results:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.

IntroductionCurrent object oriented programming languages (OOPLs) rely on mono-method dispatching.Recent research has identified multi-methods as a new, powerful feature to be added to OOPLs, and several experimental OOPLs now have multi-methods.Their ultimate success and impact in practice depends, among other things, on whether multimethod dispatching can be supported efficiently.We show that the multi-method dispatching problem can be transformed to a geometric problem on multi-dimensional integer grids, for which we then develop a data structure that uses near-linear space and has log-logarithmic query time.This gives a solution whose performance almost matches that of the best known algorithm for mono-method dispatching.

We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d, the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d \\Gamma 1 for pairs of robots, and d \\Gamma 2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the st...

We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.

We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our algorithms is $O(nk+n\alpha(n)\log n)$ for the planarcase and O(nk 2 + n log 3 n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the Amk-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n-k)log n + n log 3 n).

In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the cast consists of two parts and address the following problems. (1) Given a cast for an object and a direction , can the cast be partitioned into two parts such that the parts can be removed in directions and - , respectively, without colliding with the object or the other cast part? (2) How can one find a direction such that the above cast partitioning can be done? We give necessary and sufficient conditions for both problems, as well as algorithms to decide them for polyhedral objects. We also give some evidence that the case where the cast parts need not be removed in opposite directions is considerably harder.

Many algorithms developed in computationid geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypathetical inputs.To avoid this, realistic models are needed that describe the properties that realistic inputs have, so that algorithms can de designed that take advantage of these properties.This can lead to algorithms that are provably efficient in realktic situations.We obtain some fundamental results in this research direction.In particular, we have the following results.. We show the relations between various models that have been proposed in the literature.q For several of these models, we give algorithms to compute the model parameter(s) for a given scene; these algorithms can be used to verify whether a model is appropriate for typical scenesin some application area.q As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scenes often encountered in GIS, namely certain triangulated irregular networks.

This paper discusses some trends and achievements in computational geometry during the past five years, with emphasis on problems related to computer graphics. Furthermore, a direction of research in computational geometry is discussed that could help in bringing the fields of computational geometry and computer graphics closer together.

In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first search on the subdivision, using local criteria for deciding what is the next cell to visit. Our method is extremely simple and provably correct. The algorithm has applications in the field of geographic information systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible. We show how to adapt our algorithm to answer related queries, such as windowing queries and reporting connected subsets of cells that have a common attribute. Finally, we show how to extend our algorithm such that it can handle convex threedimensional subdivisions.

In this note we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack.We do this by performing a depth-first search on the subdivision, using local criteriafor deciding what is the next cell to visit.Our method is extremely simple.The algorithm has applications in the field of Geographic Information Systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible.We can adapt our algorithm to answer related queries, such as windowing queries, reporting connected subsets of cells that have a common attribute, and reporting in 3-dimensional convex subdivisions.

No abstract available.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region Rα(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of Rα(S) is O(nα5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional space. If each pair of curves intersects in at most s points, the expected running time of the algorithm is O(k2λs(n/k)+min(λs(n)log2n,k2λs(n/k)logn)). For the three-dimensional case the expected running time is O(nk2+min(nlog3n,nk2logn)). The algorithm also works for computing the ≤k-level in a set of discs, with an expected running time of O(nk+min(nlog2n,nklogn)). Furthermore, we give a simple algorithm for computing the order-k Voronoi diagram of a set of n points in the plane that runs in expected time O(k(n−k)logn+nlog3n).

We prove that, for any constant ε>0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n2+ε+K), where K is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to be O(n2+ε). These bounds are almost tight in the worst case.

We introduce a new type of randomized incremental algorithms.Con trary to standard randomized incremental al-

A depth order on a set of line segments in 3-space is an order such that line segment a comes before line segment $a'$ in the order when a lies below $a'$ or, in other words, when there is a vertical ray that first intersects $a'$ and then intersects a. Efficient algorithms for the computation and verification of depth orders of sets of n line segments in 3-space are presented. The algorithms run in time $O(n^{{4 / 3} + \varepsilon } )$, for any fixed $\varepsilon > 0$. If all line segments are axis-parallel or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in $O(n\log ^3 n)$, for any fixed $\varepsilon > 0$ time and the verification takes $O(n\log ^2 n)$ time. The algorithms can be generalized to handle triangles and other polygons instead of line segments. They are based on a general framework for computing and verifying linear orders extending implicitly defined binary relations.

In this paper we study the following generalization of the classical hidden surface removal problem: given a set S of objects, a view point and a point light source, compute which parts of the objects in S are visible, subdivided into parts that are lit and parts that are not lit. We prove

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in Rd.It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting of 0(nId-l)ld/2+1~) segments.The bound cannot be improved below Q(nd); thus in R3, the answer is between n3 and n4.For disjoint obstacles, a ~(n) bound is proved.By a well-known reduction, thegeneralca.seresult also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles.In the planar case, asymptotically tight bounds and efficient algorithms are given.1

A depth order on a set of objects is an order such that object a comes before object a′ in the order when a′ lies behind a′, or, in other words, when a is (partially) hidden by a′ by a′. We present efficient algorithms for the computation and verification of depth orders of sets of n rods in 3–space. Our algorithms run in time O(n4/3+ε), for any fixed ε > 0). If all rods are axis-parallel, or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in O(n log2 n) time. The algorithms can be generalized to handle triangles and other polygons instead of rods. They are based on a general framework for computing and verifying linear extensions of implicitly defined binary relations.

No abstract available.

In this paper, a data structure is given for higher dimensional shortest path queries.For a set of n axisparallel boxes in d-space and a fixed target, it is possible with this sttucturc to find a shortest rectilinear path from any point in d-space to this target, where the path does not cross any box.Alternatively, it is possible to find the length of the path.The metric considered is a generalization of the L1 -metric and the link metric, where the length of a path is its L1-length plus some (fixed) constant times the number of turns on the path.The data structure uses O ((n log n)d-l ) space to store, and a query takes O (logd-1 n) time (plus the output size if the path must be reported).As a byproduct a solution to the single shot problem is obtained; the shortest path between two given points can be computed in time O (nd log n).

An efficient, output-sensitive method for computing the visibility map of a set of axis-parallel polyhedra (i.e. polyhedra with their faces and edges parallel to the coordinate axes) as seen from a given viewpoint is introduced. For nonintersecting polyhedra with n edges in total, the algorithm runs in time O((n+k)log n), where k is the complexity of the visibility map. The method can handle cyclic overlap of the polyhedra and perspective views without any problem. For c-oriented polyhedra (with faces and edges in c orientations, for some constant c) the method can be extended to run in the same time bound. The method can be extended even further to deal with intersecting polyhedra with only a slight increase in the time bound.>