Search

For a set Q of points in the plane and a real number δ ≥ 0 , let G δ (Q) be the graph defined on Q by connecting each pair of points at distance at most δ .We consider the connectivity of G δ (Q) in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem: given a set P of n - k points in the plane and a set S of k line segments in the plane, find the minimum δ ≥ 0 with the property that we can select one point p s ∈ s for each segment s ∈ S and the corresponding graph G δ (P ∪ { p s ∣ s ∈ S }) is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in O (f (k) n log n) time, for a computable function f (·) . This implies that the problem is FPT when parameterized by k. The best previous algorithm uses O ((k !) k k k + 1 · n 2 k) time and computes the solution up to fixed precision. [ABSTRACT FROM AUTHOR]

For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least C n / 2 different plane perfect matchings, where C n / 2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k ≤ 1 64 n 2 - 35 32 n n + 1225 64 n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 5 72 n 2 - n 4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k = 0 , 1 , 2 , and maximize the number of perfect matchings with n / 2 2 crossings and with n / 2 2 - 1 crossings. [ABSTRACT FROM AUTHOR]

Let P = { p 0 , ... , p n - 1 } be a set of points in R 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 G 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 G 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 G r has a broadcast tree rooted at the first point p 0 . Our results include the following. We prove that already in R 1 , 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 R 1 and R 2 , 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 R 2 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 FROM AUTHOR]

We examine the problem of discovering the set P of points in a given topology that constitutes a k-median set for that topology, while maintaining location privacy. That is, there exists a set U of points in a d-dimensional topology for which a k-median set must be found by some algorithm A, without disclosing the location of points in U to the executor of A. We define a privacy preserving data model for a coordinate system we call a "Topology Descriptor Grid", and show how it can be used to find the rectilinear 1-median of the system and a constant factor approximation for the Euclidean 1-median. We achieve a constant factor approximation for the rectilinear 2-median of a grid topology. Additionally we show upper and lower bounds for the k-center problem. [ABSTRACT FROM AUTHOR]

We consider the problem of subset selection for ℓ p subspace approximation and (k, p)-clustering. Our aim is to efficiently find a small subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. For ℓ p subspace approximation, previously known subset selection algorithms based on volume sampling and adaptive sampling proposed in Deshpande and Varadarajan (STOC'07, 2007), for the general case of p ∈ [ 1 , ∞) , require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for ℓ p subspace approximation, for any p ∈ [ 1 , ∞) . Earlier subset selection algorithms that give a one-pass multiplicative (1 + ϵ) approximation work under the special cases. Cohen et al. (SODA'17, 2017) gives a one-pass subset section that offers multiplicative (1 + ϵ) approximation guarantee for the special case of ℓ 2 subspace approximation. Mahabadi et al. (STOC'20, 2020) gives a one-pass noisy subset selection with (1 + ϵ) approximation guarantee for ℓ p subspace approximation when p ∈ { 1 , 2 } . Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any p ∈ [ 1 , ∞) . We also focus on (k, p)-clustering, where the task is to group the data points into k clusters such that the sum of distances from points to cluster centers (raised to the power p) is minimized for p ∈ [ 1 , ∞) . The subset selection algorithms are based on D p sampling due to Wei (NIPS'16, 2016) which is an extension of D 2 sampling proposed in Arthur and Vassilvitskii (SODA'07, 2007). Due to the inherently adaptive nature of the D p sampling, these algorithms require taking multiple passes over the input. In this work, we suggest one pass subset selection for (k, p)-clustering that gives constant factor approximation with respect to the optimal solution with an additive approximation guarantee. Bachem et al. (NIPS'16, 2016) also gives one pass subset selection for k-means for p = 2 ; however, our result gives a solution for a more generic problem when p ∈ [ 1 , ∞) . At the core, our contribution lies in showing a one-pass MCMC-based subset selection algorithm such that its cost incurred due to the sampled points closely approximates the corresponding optimal cost, with high probability. [ABSTRACT FROM AUTHOR]

We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the normal play variant, the first player unable to move loses. In the scoring variant, each player aims to maximise their score, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are PSPACE-complete. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and v σ (v) ∈ E (G) for any non-fixed point v ∈ V (G) . Andres et al. (Theor Comput Sci 795:312–325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete. [ABSTRACT FROM AUTHOR]

We study the problem of how to split many point sets in R d into smaller parts using a few (shared) splitting hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization. [ABSTRACT FROM AUTHOR]

We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α -shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets. [ABSTRACT FROM AUTHOR]

This paper studies empty squares in arbitrary orientation among a set P of n points in the plane. We prove that the number of empty squares with four contact pairs is between Ω (n) and O (n 2) , and that these bounds are tight, provided P is in general position. A contact pair of a square is a pair of a point p ∈ P and a side ℓ of the square with p ∈ ℓ . The upper bound O (n 2) also applies to the number of empty squares with four contact points. Meanwhile, the lower bound becomes 0 as we can construct a point set among which there is no square of four contact points. These combinatorial results are based on new observations on the L ∞ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the L ∞ Voronoi diagram of P, while the axes of the plane continuously rotate by 90 degrees, and simultaneously reports all empty squares with four contact pairs among P in an output-sensitive way within O (s log n) time and O(n) space, where s denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among P and a square annulus of minimum width or minimum area that encloses P over all orientations can be computed in worst-case O (n 2 log n) time. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in the plane where each point p of P is associated with a radius r p > 0 . The transmission graph G = (P , E) of P is defined as the directed graph such that E contains an edge from p to q if and only if | p q | ≤ r p for any two points p and q in P, where |pq| denotes the Euclidean distance between p and q. In this paper, we present a data structure of size O (n 5 / 3) such that for any two points in P, we can check in O (n 2 / 3) time if there is a path in G between the two points. This is the first data structure for answering reachability queries whose performance depends only on n but not on the ratio between the largest and smallest radii. [ABSTRACT FROM AUTHOR]

The dispersion of a point set P ⊂ [ 0 , 1 ] d is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect P. It was observed only recently that, for any ε > 0 , certain randomized constructions provide point sets with dispersion smaller than ε and number of elements growing only logarithmically in d. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in d. Note that, however, the running-time will be super-exponential in ε - 1 . Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certain k-restriction problems, which are well-known in coding theory. [ABSTRACT FROM AUTHOR]

We revisit the online Unit Clustering and Unit Covering problems in higher dimensions: Given a set of n points in a metric space, that arrive one by one, Unit Clustering asks to partition the points into the minimum number of clusters (subsets) of diameter at most one; whereas Unit Covering asks to cover all points by the minimum number of balls of unit radius. In this paper, we work in R d using the L ∞ norm. We show that the competitive ratio of any online algorithm (deterministic or randomized) for Unit Clustering is Ω (d) . In particular, it depends on the dimension d, and this resolves an open problem raised by Epstein and van Stee (Theor Comput Sci 407(1–3):85–96, 2008). We also give a randomized online algorithm with competitive ratio O (d 2) for Unit Clustering of integer points (i.e., points in Z d , d ∈ N , under the L ∞ norm). We show that the competitive ratio of any deterministic online algorithm for Unit Covering is at least 2 d . This ratio is the best possible, as it can be attained by a simple deterministic algorithm that assigns points to a predefined set of unit hypercubes. We complement these results with some additional lower bounds for related problems in higher dimensions. [ABSTRACT FROM AUTHOR]

Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α -ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 2 π / 3 (however, our approximation ratios hold for any α ⩾ 2 π / 3 ). The α -minimum spanning tree problem asks for an α -ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α -ST of length at most 6 times the length of the minimum spanning tree (MST). By adapting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. To examine what is possible with non-uniform wedge angles, we define an α ¯ -ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α . We present an algorithm to find an α ¯ -ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α . Our algorithm runs in linear time after computing the MST. [ABSTRACT FROM AUTHOR]

Given a finite set of weighted points in R d (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in d = 1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For d = 2 , we consider that each point is colored red or blue, where red points have weight + 1 and blue points weight - ∞ . The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane. [ABSTRACT FROM AUTHOR]

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R , we define G ∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R ∈ R , the graph G ∩ R is a t-spanner for K (P) ∩ R , where K (P) is the complete geometric graph on P. For any set P of n points and any constant ε > 0 , we prove that P admits local (1 + ε) -spanners of sizes O (n log 6 n) and O (n log n) w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local (1 + ε) -spanners with O(n) edges and O (n log 2 n) edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively. [ABSTRACT FROM AUTHOR]

Let P be a set of n colored points in the d-dimensional Euclidean space. Introduced by Hart (1968), a consistent subset of P, is a set S ⊆ P such that for every point p in P \ S , the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been significant progress from the algorithmic point of view. In this paper we present the following algorithmic results for the consistent subset problem in the plane: (1) The first subexponential-time algorithm for the consistent subset problem. (2) An O (n log n) -time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Along the way we prove the following result which is of an independent interest: given n translations of a cone (defined as the intersection of n halfspaces) and n points in R 3 , in O (n log n) time one can decide whether or not there is a point in a cone. (3) An O (n log 2 n) -time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O (n 2) running time which is due to Wilfong (SoCG 1991). (4) An O(n)-time algorithm for the consistent subset problem on collinear points that are given from left to right; this improves the previous best known O (n 2) running time. (5) A non-trivial O (n 6) -time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines. To obtain these results, we combine tools from planar separators, paraboloid lifting, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, minimum covering of a circle with arcs, and several geometric transformations. [ABSTRACT FROM AUTHOR]

A bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O (n 2.5 log n) -time, where n = | A | + | B | . This result significantly reduces the gap between the Ω (n 7) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O (n 2) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP -hard, and provide efficient algorithms to solve it on important subclasses. [ABSTRACT FROM AUTHOR]

Consider a set P ⊆ R d of n points, and a convex body C provided via a separation oracle. The task at hand is to decide for each point of P if it is in C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using queries, where is the size of the largest subset of points of P in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using oracle queries, where is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C contains all points of P . As an application of the above, we show that the discrete geometric median of a point set P in R 2 can be computed in expected time. [ABSTRACT FROM AUTHOR]

In this article, we study some fault-tolerant covering problems in metric spaces. In the metric multi-cover problem (MMC), we are given two point sets Y (servers) and X (clients) in an arbitrary metric space (X ∪ Y , d) , a positive integer k that represents the coverage demand of each client, and a constant α ≥ 1 . Each server can host a single ball of arbitrary radius centered on it. Each client x ∈ X needs to be covered by at least k such balls centered on servers. The objective function that we wish to minimize is the sum of the α -th powers of the radii of the balls. We also study some non-trivial generalizations of the MMC, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the t-MMC, where we require the number of open servers to be at most some given integer t. We present the first constant approximations for these fault-tolerant covering problems. Our algorithms are based on the following paradigm: for each of the three problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding 1-covering problem, where the coverage demand of each client is 1. The reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for 1-covering, we obtain our results for the MMC and these generalizations. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following sum query problem: Given a point set P in R d , and a distance-based function f(p, q) (i.e., a function of the distance between p and q) satisfying some general properties, the goal is to develop a data structure and a query algorithm for efficiently computing a (1 + ϵ) -approximate solution to the sum ∑ p ∈ P f (p , q) for any query point q ∈ R d and any small constant ϵ > 0 . Existing techniques for this problem are mainly based on some core-set techniques which often have difficulties to deal with functions with local domination property. Based on several new insights to this problem, we develop in this paper a novel technique to overcome these encountered difficulties. Our algorithm is capable of answering queries with high success probability in time no more than O ~ ϵ , d (n 0.5 + c) , and the underlying data structure can be constructed in O ~ ϵ , d (n 1 + c) time for any c > 0 , where the hidden constant has only polynomial dependence on 1 / ϵ and d. Our technique is simple and can be easily implemented for practical purpose. [ABSTRACT FROM AUTHOR]

Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O (n log log n + m log m) -time algorithm to compute the geodesic farthest-point Voronoi diagram of m point sites in a simple n-gon. This improves the previously best known algorithm by Aronov et al. (Discrete Comput Geom 9(3):217–255, 1993). In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in O ((n + m) log log n) time. [ABSTRACT FROM AUTHOR]

Let P ⊂ R d be a set of n points in d dimensions such that each point p ∈ P has an associated radius r p > 0 . The transmission graphG for P is the directed graph with vertex set P such that there is an edge from p to q if and only if | p q | ≤ r p , for any p , q ∈ P . A reachability oracle is a data structure that decides for any two vertices p , q ∈ G whether G has a path from p to q. The quality of the oracle is measured by the space requirement S(n), the query time Q(n), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in O (n log n) time an oracle with Q (n) = O (1) and S (n) = O (n) . For planar point sets, the ratio Ψ between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on Ψ : the first works only for Ψ < 3 and achieves Q (n) = O (1) with S (n) = O (n) and preprocessing time O (n log n) ; the second data structure gives Q (n) = O (Ψ 3 n) and S (n) = O (Ψ 3 n 3 / 2) ; the third data structure is randomized with Q (n) = O (n 2 / 3 log 1 / 3 Ψ log 2 / 3 n) and S (n) = O (n 5 / 3 log 1 / 3 Ψ log 2 / 3 n) and answers queries correctly with high probability. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of constrained clustering problems of points in R d , where d could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called Peeling-and-Enclosing, to iteratively solve two variants of the constrained clustering problems, constrained k-means clustering (k-CMeans) and constrained k-median clustering (k-CMedian). Our framework generalizes Kumar et al.'s (J ACM 57(2):5, 2010) elegant k-means clustering approach from unconstrained data to constrained data, and is based on two standalone geometric techniques, called Simplex Lemma and Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. If k and 1 ϵ are fixed numbers, our framework generates, in nearly linear time (i.e., O (n (log n) k + 1 d) ), O ((log n) k) k-tuple candidates for the k mean or median points, and one of them induces a (1 + ϵ) -approximation for k-CMeans or k-CMedian, where n is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best k-tuple candidate), we obtain a (1 + ϵ) -approximation for each of the constrained clustering problems. Our framework improves considerably the best known results for these problems. We expect that our technique will be applicable to other variants of k-means and k-median clustering problems without locality. [ABSTRACT FROM AUTHOR]

The input for the Geometric Coverage problem consists of a pair Σ = (P , R) , where P is a set of points in R d and R is a set of subsets of P defined by the intersection of P with some geometric objects in R d . Motivated by what are called choice problems in geometry, we consider a variation of the Geometric Coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution. As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. Our main result is that as long as the conflict graph has bounded arboricity there is a parameterized reduction to the conflict-free version. As a consequence, we have the following results when the conflict graph has bounded arboricity. (1) If the Geometric Coverage problem is fixed parameter tractable (FPT), then so is the conflict free version. (2) If the Geometric Coverage problem admits a factor α -approximation, then the conflict free version admits a factor α -approximation algorithm running in FPT time. As a corollary to our main result we get a plethora of approximation algorithms that run in FPT time. Our other results include an FPT algorithm and a hardness result for conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid. We prove that conflict-free version of Covering Points by Intervals does not admit an FPT algorithm, unless FPT =W[1], for the family of conflict graphs for which the Independent Set problem is W[1]-hard. [ABSTRACT FROM AUTHOR]

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an O (n + h log h) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of an L 1 shortest obstacle-avoiding path from s to t can be computed in O (log n) time and the actual path can be reported in additional time proportional to the number of edges of the path. The previously best algorithm computes such a shortest path map in O (n log n) time and O(n) space. So our algorithm is faster when h is relatively small. Further, our techniques can be extended to obtain improved results for other related problems, e.g., computing the L 1 geodesic Voronoi diagram for a set of point sites among the obstacles. [ABSTRACT FROM AUTHOR]

Let P be a finite set of points in the plane and S a set of non-crossing line segments with endpoints in P. The visibility graph of P with respect to S, denoted Vis (P , S) , has vertex set P and an edge for each pair of vertices u, v in P for which no line segment of S properly intersects uv. We show that the constrained half- θ 6 -graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of Vis (P , S) . We then show how to construct a plane 6-spanner of Vis (P , S) with maximum degree 6 + c , where c is the maximum number of segments of S incident to a vertex. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets A and B, in the plane, with m=|B|≪n=|A|, in the partial-matching setup, in which each point in B is matched to a distinct point in A. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision DB,A of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is O(n2m3.5(elnm+e)m), so it is only quadratic in |A|. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. [ABSTRACT FROM AUTHOR]

We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an ${\mathcal {O}}(1)$-approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent ℓ≥1, we obtain a randomized ${\mathcal {O}}(1)$-approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits. [ABSTRACT FROM AUTHOR]

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− ε. [ABSTRACT FROM AUTHOR]

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ( nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ( n) time algorithm. Then, we show how to solve the weighted version of this problem in time O( nlog n). Finally, we give an O( nhlog n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k. [ABSTRACT FROM AUTHOR]

We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝ using O((1/ ε)log (1/ ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ ε) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc. [ABSTRACT FROM AUTHOR]