Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

For a polygon P with holes in the plane, we denote by ϱ(P) the ratio between the geodesic and the Euclidean diameters of P. It is shown that over all convex polygons with h convex holes, the supremum of ϱ(P) is between Ω(h1/3) and O(h1/2) . The upper bound improves to O(1+min{h3/4Δ,h1/2Δ1/2}) if every hole has diameter at most Δ⋅diam2(P) ; and to O(1) if every hole is a fat convex polygon. Furthermore, we show that the function g(h)=supPϱ(P) over convex polygons with h convex holes has the same growth rate as an analogous quantity over geometric triangulations with h vertices when h→∞more » « lessFree, publiclyaccessible full text available June 3, 2024

Given a set S of n points in the plane and a parameter ε>0, a Euclidean (1+ε) spanner is a geometric graph G=(S,E) that contains a path of weight at most (1+ε)∥pq∥2 for all p,q∈S . We show that the minimum weight of a Euclidean (1+ε)spanner for n points in the unit square [0,1]2 is O(ε−3/2n−−√), and this bound is the best possible. The upper bound is based on a new spanner algorithm that sparsifies Yaographs. It improves upon the baseline O(ε−2n−−√), obtained by combining a tight bound for the weight of an MST and a tight bound for the lightness of Euclidean (1+ε)spanners, which is the ratio of the spanner weight to the weight of the MST. The result generalizes to dspace for all d∈N : The minimum weight of a Euclidean (1+ε)spanner for n points in the unit cube [0,1]d is Od(ε(1−d2)/dn(d−1)/d), and this bound is the best possible. For the n×n section of the integer lattice, we show that the minimum weight of a Euclidean (1+ε)spanner is between Ω(ε−3/4n2) and O(ε−1log(ε−1)n2). These bounds become Ω(ε−3/4n−−√) and O(ε−1log(ε−1)n−−√) when scaled to a grid of n points in [0,1]2. .more » « less

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

null (Ed.)Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)spanners of lightness O(ε^{1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{d/2}) for the lightness of Steiner (1+ε)spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2. In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)spanner of lightness O(ε^{1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.more » « less

null (Ed.)Lightness and sparsity are two natural parameters for Euclidean (1+ε)spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in dspace admits an (1+ε)spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)spanner. They gave upper bounds of Õ(ε^{(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{(d1))/2}) for the minimum sparsity in dspace for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)spanners of lightness O(ε^{1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{d/2}) for the lightness and Ω(ε^{(d1)/2}) for the sparsity of such spanners in Euclidean dspace for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)spanners of lightness O(ε^{1}log n) for n points in Euclidean plane.more » « less

null (Ed.)Imagine t ≤ mn unitsquare tiles in an m×n rectangular box that you can tilt to cause all tiles to slide maximally in one of the four orthogonal directions. Given two tiles of interest, is there a tilt sequence that brings them to adjacent squares? We give a lineartime algorithm for this problem, motivated by 2048 endgames. We also bound the number of reachable configurations, and design instances where all t tiles permute according to a cyclic permutation every four tilts.more » « less

null (Ed.)Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected kPartition with slack s, denoted (k, s)BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with ni−n/k≤s , each of which induces a connected subgraph (when s=0 , the k parts are perfectly balanced, and we call it kBCP for short). A recombination is an operation that takes a (k, s)BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two kBCPs, A and B, of G and a slack s≥0 , we wish to determine whether there exists a sequence of recombinations that transform A into B via (k, s)BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k , and (3) we provide negative instances for s≤n/(3k) . (4) We show that the problem is PSPACEcomplete when k∈O(nε) and s∈O(n1−ε) , for any constant 0<ε≤1 , even for restricted settings such as when G is an edgemaximal planar graph or when k≥3 and G is planar.more » « less

null (Ed.)We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A=(α0,…,αn−1) , αi∈(−π,π) , for i∈{0,…,n−1} . The problem of realizing A by a polygon can be seen as that of constructing a straightline drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P⊂R2 realizing A has at least c crossings, for every c∈N , and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P⊂R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P⊂R3 , and for every realizable sequence the algorithm finds a realization.more » « less