Given a simple polygon P with n vertices, we consider the problem of constructing a data structure for visibility queries: for any query point q ∈ P, compute the visibility polygon of q in P. To obtain O(log n + k) query time, where k is the size of the visibility polygon of q, the previous best result requires O(n³) space. In this paper, we propose a new data structure that uses O(n^{2+ε}) space, for any ε > 0, while achieving the same query time. If only O(n²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) space, the only previously known approach, aside from the O(n)-time algorithm that computes the visibility polygon without preprocessing, is an O(n)-space data structure that supports O(k log n)-time queries. We construct a data structure using O(n log n) space that answers visibility queries in O(n^{1/2+ε} + k) time. In addition, for the special case in which q lies on the boundary of P, we build a data structure of O(n log n) space supporting O(log² n + k) query time; alternatively, we achieve O(log n + k) query time using O(n^{1+ε}) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Abstract Given a point set P in the Euclidean plane and a parameter t , we define an oriented t -spanner G as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in G through those points is at most a factor t longer than the shortest cycle in the complete graph on P . We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in $$\mathcal {O}(n^7)$$ time for n points, and a greedy algorithm that computes a 5-spanner in $$\mathcal {O}(n\log n)$$ time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in a plane oriented t -spanner with $$t=7.2 \cdot t_g$$ , where $$t_g$$ is an upper bound on the dilation of the greedy triangulation.

The problem of locally routing on geometric networks using limited memory is extensively studied in computational geometry. We consider one particular graph, the ordered Θ-graph, which is significantly harder to route on than the Θ-graph, for which a number of routing algorithms are known. Currently, no local routing algorithm is known for the ordered Θ-graph. We prove that, unfortunately, there does not exist a deterministic memoryless local routing algorithm that works on the ordered Θ-graph. This motivates us to consider allowing a small amount of memory, and we present a deterministic O (1)-memory local routing algorithm that successfully routes from the source to the destination on the ordered Θ-graph. We show that our local routing algorithm converges to the destination in O ( n ) hops, where n is the number of vertices. To the best of our knowledge, our algorithm is the first deterministic local routing algorithm that is guaranteed to reach the destination on the ordered Θ-graph.

The c-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in c-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the c-packedness assumption, and more specifically, on c-packed graphs. In this paper, we prove two fundamental properties of c-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size.

We consider the problem of computing an approximate weighted shortest path in a weighted planar subdivision, with weights assigned from the set {0, 1, ∞}. The subdivision includes zero-cost regions (0-regions) with weight 0 and obstacles with weight ∞, all embedded in a plane with weight 1. In a polygonal domain, where the 0-regions and obstacles are non-overlapping polygons (not necessarily convex) with in total N vertices, we present an algorithm that computes a (1 + ε)-approximate spanner of the input vertices in expected Oe(N/ε3) time1, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Oe(N/ε3) time. Furthermore, we prove that our results more generally apply to non-polygonal convex regions. Using this generalisation, one can approximate the weak partial Fréchet similarity [7] between two polygonal curves in expected Oe(n2/ε2) time, where n is the total number of vertices of the input curves.

Abstract Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio $$A$$ A have spanning ratio at most $$\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}$$ 2 1 + A 2 + A A 2 + 1 , which matches the known lower bound.

Given a set of n ≥ 1 unit disk robots in the Euclidean plane , we consider the Pattern Formation problem, i.e., the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. Recently, this problem was solved in the asynchonous model for fat robots that agree on at least one axis in the robots with lights model where each robot is equipped with an externally visible persistent light that can assume colors from a fixed set of colors [1] . In this work, we reduce the number of colors needed and remove the axis-agreement requirement in the fully synchronous model. In particular, we present an algorithm requiring 7 colors when scaling the target pattern is allowed and an 8-color algorithm if scaling is not allowed. Our algorithms run in O ( n ) + O ( q log ⁡ n ) rounds with probability at least 1 − n − q .

Given a set of n ≥ 1 autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane , we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small O ( 1 ) -sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in O ( n ) + O ( q log ⁡ n ) rounds with probability at least 1 − n − q . The algorithms are collision-free and do not require the knowledge of the number of robots.

We present sweeping line graphs, a generalization of Θ-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.

Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented 𝒪(1)-spanner.

Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio A have spanning ratio at most √2 √{1+A² + A √{A²+1}}, which matches the known lower bound.

We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. At least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c · r in length. Previous results by Gudmundsson and Wong [24] established an Ω(n3) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n3 log2 n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c2n/ε2) log(c/ε) log(n/ε)) time complexity.

Abstract. We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks, we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.

Abstract Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have $$\varOmega (n)$$ Ω ( n ) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses $$O(n^2)$$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ⁡ ( n ω , n 2 + n h log ⁡ h + χ 2 ) ) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log ⁡ n ) time.

We study how to dynamize the Trapezoidal Search Tree - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. Moreover, the dynamization carries over to the Trapezoidal Search DAG, offering a linear sized data structure with logarithmic point location costs as a by-product. On a set $S$ of non-crossing segments, each update performs expected ${\mathcal O}(\log^2|S|)$ operations. We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.

Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of n disks in the plane. Initially, all disks have radius 0, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is O ( n ( log ⁡ n + min ⁡ { log ⁡ Δ , log ⁡ Φ } ) ) , where Δ is the ratio of the fastest and the slowest growth rate and Φ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an Ω ( n log ⁡ n ) lower bound, showing that our quadtree algorithms are almost tight.

Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.

We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

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.

In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $$d>0$$ , the first algorithm maintains a proper $$O(\mathcal {C} dN ^{1/d})$$ -coloring while recoloring at most O(d) vertices per update, where $$\mathcal {C} $$ and $$N $$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $$O(\mathcal {C} d)$$ -coloring with $$O(dN ^{1/d})$$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a c-coloring of a 2-colorable graph on $$N $$ vertices must recolor at least $$\varOmega (N ^\frac{2}{c(c-1)})$$ vertices per update, for any constant $$c \ge 2$$ .

We show that for any set of n moving points in R^d and any parameter 2<=k

We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph (the half-$\theta_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3} \approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2, meaning that even though there always exists a path whose length is at most twice the Euclidean distance, we cannot always find such a path when routing locally. Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder's embedding scheme [W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 1990), ACM, New York, SIAM, Philadelphia, 1990, pp. 138--148], our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3} \approx 8.660$ on two bounded degree subgraphs of the half-$\theta_6$-graph.

For a set of points in the plane and a fixed integer k > 0, the Yao graph Yk partitions the space around each point into k equiangular cones of angle θ = 2π/k, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of Y5, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd k ≥ 5, the spanning ratio of Yk is at most 1/(1−2sin(3θ/8)), which gives the first constant upper bound for Y5, and is an improvement over the previous bound of 1/(1−2sin(θ/2)) for odd k ≥ 7. We further reduce the upper bound on the spanning ratio for Y5 from 10.9 to 2 + √3 ≈ 3.74, which falls slightly below the lower bound of 3.79 established for the spanning ratio of ⊝5 (⊝-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and ⊝-graph with the same number of cones. We also give a lower bound of 2.87 on the spanning ratio of Y5. Finally, we revisit the Y6 graph, which plays a particularly important role as the transition between the graphs (k > 6) for which simple inductive proofs are known, and the graphs (k ≤ 6) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of Y6 from 17.6 to 5.8, getting closer to the spanning ratio of 2 established for ⊝6.

We present a deterministic local routing scheme that is guaranteed to find a path between any pair of vertices in a half-θ6-graph whose length is at most 5/ √ 3 = 2.886... times the Euclidean distance between the pair of vertices.The half-θ6graph is identical to the Delaunay triangulation where the empty region is an equilateral triangle.Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal.This is somewhat surprising because the spanning ratio of the half-θ6-graph is 2. Since every triangulation can be embedded in the plane as a half-θ6-graph using O(log n) bits per vertex coordinate via Schnyder's embedding scheme (SODA 1990), our result provides a competitive local routing scheme for every such embedded triangulation.