Search

We initiate the study of a generalization of the class cover problem [Cannon and Cowen [1] , Bereg et al. [2] ] the generalized class cover problem , where we are allowed to misclassify some points provided we pay an associated positive penalty for every misclassified point. Two versions: single coverage and multiple coverage , of the generalized class cover problem are investigated. We study five different variants of both versions of the generalized class cover problem with axis-parallel strips and axis-parallel half-strips extending to different directions in the plane, thus extending similar work by Bereg et al. (2012) [2] on the class cover problem. We prove that the multiple coverage version of the generalize class cover problem with axis-parallel strips are in P , whereas the single coverage version is NP -hard. A factor 2 approximation algorithm is provided for the later problem. The APX -hardness result is also shown for the single coverage version. For half-strips extending to exactly one direction, both the single and multiple coverage versions can be solved in polynomial time using dynamic programming. In the case of half-strips extending to two orthogonal directions, we prove the class cover problem is NP -hard followed by APX -hard. This gives improve hardness results compare to Bereg et al. (2012) [2] , where they proved the class cover problem with half-strips oriented in four different directions is NP -hard. These NP - and APX -hardness results can directly apply to both single and multiple versions. Finally, constant factor approximation algorithms are provided for half-strips extending to more than one direction. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance (d G H) proves to be a useful distance measure between shapes. In order to approximate d G H for X , Y ⊂ R d , we look into its relationship with d H , i s o , the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d ≥ 2 , d H , i s o cannot be bounded above by a constant factor times d G H. For d = 1 , however, we prove that d H , i s o ≤ 5 4 d G H. We also show that the bound is tight. In effect, for X , Y ⊂ R with at most n points, this gives rise to an O (n log ⁡ n) -time algorithm to approximate d G H (X , Y) with an approximation factor of (1 + 1 4). [ABSTRACT FROM AUTHOR]

This paper addresses a family of geometric half-plane retrieval queries of points in the plane in the presence of geometric uncertainty. The problems include exact and uncertain point sets and half-plane queries defined by an exact or uncertain line whose location uncertainties are independent or dependent and are defined by k real-valued parameters. Point coordinate uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), an expressive and computationally efficient worst-case, first order linear approximation of geometric uncertainty that supports parametric dependencies between point locations. We present an efficient O (k 2) time and space algorithm for computing the envelope of the LPGUM line that defines the half-plane query. For an exact line and an LPGUM n points set, we present an O (log ⁡ n k + m k) time query and O (n k) space algorithm, where m is the number of LPGUM points on or above the half-plane line. For a LPGUM line and an exact points set, we present a O (k 2 + (k log ⁡ n log ⁡ log ⁡ n) ε + m) time and O ( n 2 log ⁡ n + k ε) space approximation algorithm, where 0 < ε ≤ 1 is the desired approximation error. For a LPGUM line and an LPGUM points set, we present two O (k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε + m k) and O (m k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε) time query and O ( (n k) 2 log ⁡ n k + k ε) space approximation algorithms for the independent and dependent case, respectively. [ABSTRACT FROM AUTHOR]

We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP -hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any ϵ > 0 , there exists a (2 + ϵ) -approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first O (1) -approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L -frames : the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a (2 + ϵ) -approximation for the problem with "diagonal-anchored" L -frames. On the other hand, we show that the problem is APX -hard in case the input L -frames intersect the diagonal, or the horizontal segments of the L -frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L -frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017). [ABSTRACT FROM AUTHOR]

We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O (1) -approximation running in O (n d + 1 log ⁡ n) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O (n d) -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest. [ABSTRACT FROM AUTHOR]

We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R ′ that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1 + ε) -approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O (1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O (log ⁡ n log ⁡ log ⁡ n) -approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O (n 5 / 2 log ⁡ n) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O (n k 3 / 2 log ⁡ k) time, and (ii) an approximation algorithm that finds, in O (n + n k ε 5 log 5 / 2 ⁡ n k log ⁡ (1 ε log ⁡ n k)) time, a rectangle of the given perimeter that contains at least (1 − ε) k points of P , where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k , an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art. [ABSTRACT FROM AUTHOR]

This paper deals with constructing centralized geometric network that represents a set of clients that need to be connected to a server. We consider the problem of minimizing the sum of the shortest paths from the clients to the server in the network, subject to some constraints. We refer to this summation as the network cost. The motivation for this work was derived from the combination of centralized communication network and geometric sink spanner. Formally, given a set V of points (representing clients) in the plane, a special point q ∈ V (representing a server), a real number w > 0 (the network weight bound), and an integer h ≥ 1 (the hop bound), the goal is to construct a directed network G = (V , E) of minimum cost, such that there is a directed path from every point in V to q with at most h hops, and ∑ (v , u) ∈ E | v u | ≤ w , where | v u | denotes the Euclidean distance between v and u. In this paper we start by establishing a connection between the considered problem and geometric sink spanner network. Then, we present our main result, a bi-criteria approximation algorithm, that approximates both the weight and the cost of the network with respect to an optimal network, in (| V | / ε) O (h / ε). More precisely, we construct a network such that its cost (i.e., sum of the shortest paths from every v ∈ V to q) is at most (1 + h ε) times the cost of an optimal network and its weight (i.e., ∑ (v , u) ∈ E | v u |) is at most (1 + ε) ⋅ w , for any ε > 0. [ABSTRACT FROM AUTHOR]

Abstract We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP -complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in the plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, we say that one object is dominated by another if their intersection is nonempty. For the second problem, for a given set of points and objects in the plane, the objective is to choose a minimum number of objects to cover all the points. This is a particular version of the set-cover problem. Both problems have been well-studied, subject to various restrictions on the input objects. These problems are APX -hard for object sets consisting of axis-parallel rectangles, ellipses, α -fat objects of constant description complexity, and convex polygons. On the other hand, PTAS s (polynomial time approximation schemes) are known for object sets consisting of disks or unit squares. Surprisingly, a PTAS was unknown even for arbitrary squares. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that a popular local-search algorithm leads to a (1 + ε) approximation for a family of homothets of a convex object (which includes arbitrary squares, k -regular polygons, translated and scaled copies of a convex set, etc.) in n O (1 / ε 2) time. On the other hand, the same approach leads to a PTAS for the geometric covering problem when the objects are convex pseudodisks (which include disks, unit height rectangles, homothetic convex objects, etc.). Consequently, we obtain an easy-to-implement approximation algorithm for both problems for a large class of objects, significantly improving the best-known approximation guarantees. [ABSTRACT FROM AUTHOR]

We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5 / 3 − ϵ) -approximation algorithm, for any ϵ > 0 , unless P = N P. We also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth. [ABSTRACT FROM AUTHOR]

We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane. [ABSTRACT FROM AUTHOR]

In the barrier resilience problem (introduced by Kumar et al., Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the collection only contains fat regions with bounded ply Δ (even when they are axis-aligned rectangles of aspect ratio 1 : ( 1 + ε ) ). We also show that the problem is fixed-parameter tractable (FPT) for unit disks and for similarly-sized β -fat regions with bounded ply Δ and O ( 1 ) pairwise boundary intersections. We then use our FPT algorithm to construct an ( 1 + ε ) -approximation algorithm that runs in O ( 2 f ( Δ , ε , β ) n 5 ) time, where f ∈ O ( Δ 4 β 8 ε 4 log ⁡ ( β Δ / ε ) ) . [ABSTRACT FROM AUTHOR]

Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s ⊆ P corresponding to its trajectory . The camera sees a point p ∈ P if there is a point q ∈ s such that p q ‾ is a line segment normal to s that is completely contained in P . In the Minimum-Cardinality Sliding Cameras (MCSC) problem , the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S ), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel. In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP -complete when P is allowed to have holes, and (iii) an O ( n 3 log ⁡ n ) -time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons). [ABSTRACT FROM AUTHOR]

In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1] . For D -dimensional simplicial complexes, we obtain a ( D + 1 ) ( D 2 + D + 1 ) -factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D ≥ 5 , we describe a 2 D -factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1 2 -factor approximation for 3-manifolds and 4 9 -factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1 ( D + 1 ) -factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. [ABSTRACT FROM AUTHOR]

Given a set P of terminals in the plane and a partition of P into k subsets P 1 , … , P k , a two-level rectilinear Steiner tree consists of a rectilinear Steiner tree T i connecting the terminals in each set P i ( i = 1 , … , k ) and a top-level tree T t o p connecting the trees T 1 , … , T k . The goal is to minimize the total length of all trees. This problem arises naturally in the design of low-power physical implementations of parity functions on a computer chip. For bounded k we present a polynomial time approximation scheme (PTAS) that is based on Arora's PTAS for rectilinear Steiner trees after lifting each partition into an extra dimension. For the general case we propose an algorithm that predetermines a connection point for each T i and T t o p ( i = 1 , … , k ). Then, we apply any approximation algorithm for minimum rectilinear Steiner trees in the plane to compute each T i and T t o p independently. This gives us a 2.37-factor approximation with a running time of O ( | P | log ⁡ | P | ) suitable for fast practical computations. The approximation factor reduces to 1.63 by applying Arora's approximation scheme in the plane. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, we consider the problem of covering P with a minimum number of unit disks. This problem is known to be NP-hard. We present a simple 4-approximation algorithm for this problem which runs in O ( n log ⁡ n ) -time. We also show how to extend this algorithm to other metrics, and to three dimensions. [ABSTRACT FROM AUTHOR]

Given a set of n moving points in R d , where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O ˜ ( n 5 / 3 ) -time algorithm 1 to compute a ( 1 + ϵ ) -factor approximation to the minimum closest pair distance over time, for any constant ϵ > 0 and any constant dimension d . This addresses an open problem posed by Gupta, Janardan, and Smid [1] . More generally, we consider a data structure version of the problem: for any linearly moving query point q , we want a ( 1 + ϵ ) -factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O ˜ ( n 5 / 3 ) space and O ˜ ( n 2 / 3 ) query time, O ˜ ( n 5 ) space and polylogarithmic query time, or O ˜ ( n ) space and O ˜ ( n 4 / 5 ) query time, for any constant ϵ > 0 and any constant dimension d . 1 The notation O ˜ is used to hide polylogarithmic factors. That is, O ˜ ( f ( n ) ) = O ( f ( n ) log c ⁡ n ) , where c is a constant. [ABSTRACT FROM AUTHOR]

We give a fully dynamic data structure for maintaining an approximation of the Hausdorff distance between two point sets in a constant dimension d , a standard problem in computational geometry. Our solution has an approximation factor of 1 + ε for any constant ε > 0 and expected update time O ( log ⁡ U log ⁡ log ⁡ n ) , where U is the universe size, and n is the number of the points. The result of the paper greatly improves over the previous exact method, which required O ( n 5 / 6 polylog n ) time and worked only in a semi-online setting. The model of computation is the word RAM model. [ABSTRACT FROM AUTHOR]

We study the 2-center problem with outliers in high-dimensional data streams. Given a stream of points in arbitrary d dimensions, the goal is to find two congruent balls of minimum radius covering all but at most z points. We present a ( 1.8 + ε ) -approximation streaming algorithm, improving over the previous ( 4 + ε ) -approximation algorithm available for the problem. The space complexity and update time of our algorithm are poly ( d , z , 1 / ε ) , independent of the size of the stream. [ABSTRACT FROM AUTHOR]

Given a set of n points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-hard and several approximation algorithms have been designed over the last three decades. In this paper, we have engineered and experimentally compared practical performances of some of these algorithms on massive pointsets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present a simple 7-approximation algorithm for UDC that runs in O (n) expected time and uses O (s) extra space, where s denotes the size of the generated cover. In our experiments, it turned out to be the speediest of all. We also present two heuristics to reduce the sizes of covers generated by it without slowing it down by much. To our knowledge, this is the first work that experimentally compares algorithms for the UDC problem. Experiments with them using massive pointsets (in the order of millions) throw light on their practical uses. We share the engineered algorithms via GitHub 1 for broader uses and future research in the domain of geometric optimization. [ABSTRACT FROM AUTHOR]

Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree (minimum) spanning trees, which have received significant attention. Let P be a set of n points in the plane, and let 0 < α < 2 π be an angle. An α -spanning tree (α -ST) of P is a spanning tree of the complete Euclidean graph over P , with the following property: For each vertex p i ∈ P , the (smallest) angle that is spanned by all the edges incident to p i is at most α. An α -minimum spanning tree (α -MST) is an α -ST of P of minimum weight, where the weight of an α -ST is the sum of the lengths of its edges. In this paper, we consider the problem of computing an α -MST for the case where α = 2 π 3. We present a 4-approximation algorithm, thus improving upon the previous results of Aschner and Katz and Biniaz et al., who presented algorithms with approximation ratios 6 and 16 3 , respectively. To obtain this result, we devise an O (n) -time algorithm that, given any Hamiltonian path Π of P , constructs a 2 π 3 -ST T of P , such that T 's weight is at most twice that of Π and, moreover, T is a 3-hop spanner of Π. This latter result is optimal (with respect to T 's weight), since for any ε > 0 there exists a polygonal path for which every 2 π 3 -ST (of the corresponding set of points) has weight greater than 2 − ε times the weight of the path. [ABSTRACT FROM AUTHOR]

The art gallery problem is a classical sensor placement problem that asks for the minimum number of guards required to see every point in an environment. The standard formulation does not take into account self-occlusions caused by a person or an object within the environment. Obtaining good views of an object from all orientations despite self-occlusions is an important requirement for surveillance and visual inspection applications. We study the art gallery problem under a constraint, termed △-guarding, that ensures that all sides of any convex object are always visible in spite of self-occlusion. Our contributions in this paper are three-fold: We first prove that Ω ( n ) guards are always necessary for △-guarding the interior of a simple polygon having n vertices. Second, we present a O ( log ⁡ c opt ) factor approximation algorithm for △-guarding polygons with or without holes, when the guards are restricted to vertices of the polygon. Here, c opt is the optimal number of guards. Third, we study the problem of △-guarding a set of line segments connecting points on the boundary of the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. We present a constant factor approximation algorithm for this problem – one of the few such results for art gallery problems. [ABSTRACT FROM AUTHOR]

We provide constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k ≥ 0 , unit B k -VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. We give an 18-approximation algorithm for the MDS problem on unit B 0 -VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k 4) -approximation algorithm for the MDS problem on unit B k -VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L -graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results. [ABSTRACT FROM AUTHOR]

A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor F FPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that F FPS can be bounded in terms of the minimal value F ⁎ of the stretch factor obtained using an optimal placement of k sources as F FPS ⩽ 2 r e 2 F ⁎ + 2 r e 2 + 8 r e + 1 , where r e is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor r e is not an artefact of the analysis by providing a class of graphs for which F FPS ⩾ 1 2 r e F ⁎ . [ABSTRACT FROM AUTHOR]

A bottleneck plane perfect matching of a set of n points in R 2 is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as bottleneck . The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least n 5 in O ( n log 2 ⁡ n ) -time. Then we extend our idea toward an O ( n log ⁡ n ) -time approximation algorithm which computes a plane matching of size at least 2 n 5 whose edges have length at most 2 + 3 times the bottleneck. [ABSTRACT FROM AUTHOR]

Given a set of points P and axis-aligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the max-exposure problem , given an integer parameter k , we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP -hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple O (k) bicriteria approximation algorithm; that is by deleting O (k 2) rectangles, we can expose at least Ω (1 / k) of the optimal number of points. [ABSTRACT FROM AUTHOR]

Given an edge-weighted graph G = ( V , E ) and a subset R of V , a Steiner tree of G is a tree which spans all the vertices in R . A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G . As for λ -precise unit disk graphs we present a ( 10 + 1 λ ) -approximation algorithm, where λ is the length of the shortest edge in G . [ABSTRACT FROM AUTHOR]

We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in O*(2n) time [9], which is less than the lower bound of O(2.43n)O(2.43n) on the number of triangulations of any point set [30]. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by ? the output of our algorithm and by cncn the exact number of triangulations of P, for some positive constant c, we prove that cn=?=cn.2o(n). This is the first algorithm that in sub-exponential time computes a (1+o(1))(1+o(1))-approximation of the base of the number of triangulations, more precisely, c=?1/n=(1+o(1))c. Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees. [ABSTRACT FROM AUTHOR]

We study a geometric version of the Red-Blue Set Cover problem originally proposed by Carr et al. (2000) [1]: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers the problem of finding the cost of a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We show how the transportation network with n edges in the Euclidean plane can be preprocessed in time into a data structure of size such that -approximate quickest path cost queries between any two points in the plane can be answered in time . In addition we consider the nearest neighbor problem in a transportation network: given a transportation network with n edges in the Euclidean plane together with a set of m sites, a query point , find the nearest site in from q. We show how the transportation network can be preprocessed in time such that -nearest neighbor query can be answered in time . [Copyright &y& Elsevier]

Abstract: A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case ( ). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains. Our two main algorithms are as follows: A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains. An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm. We also obtain several related results: [•] 3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain). [•] An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones. [•] An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain. [•] A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path. [•] A notion of “robust” paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1. [Copyright &y& Elsevier]

Abstract: Let P be a set of 2n points in the plane, and let (resp., ) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P. We study the problem of computing . We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an -time algorithm that computes a non-crossing matching M of P, such that , where is the length of a longest edge in M. An interesting implication of our construction is that . Finally, we show that when the points of P are in convex position, one can compute in time, improving a result in [7]. [Copyright &y& Elsevier]

Abstract: Given a (master) set M of n points in d-dimensional Euclidean space, consider drawing a random subset that includes each point with an independent probability . How difficult is it to compute elementary statistics about the closest pair of points in such a subset? For instance, what is the probability that the distance between the closest pair of points in the random subset is no more than ℓ, for a given value ℓ? Or, can we preprocess the master set M such that given a query point q, we can efficiently estimate the expected distance from q to its nearest neighbor in the random subset? These basic computational geometry problems, whose complexity is quite well-understood in the deterministic setting, prove to be surprisingly hard in our stochastic setting. We obtain hardness results and approximation algorithms for stochastic problems of this kind. [Copyright &y& Elsevier]

Abstract: We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of for any . This result significantly narrows the gap between the best known upper bound and the lower bound of 3/2; previously, the best upper bound was 1.9396 due to Harren and van Stee. [Copyright &y& Elsevier]

Abstract: Let P be a set of points in the plane, representing transceivers equipped with a directional antenna of angle α and range r. The coverage area of the antenna at point p is a circular sector of angle α and radius r, whose orientation can be adjusted. For a given assignment of orientations, the induced symmetric communication graph (SCG) of P is the undirected graph, in which two vertices (i.e., points) u and v are connected by an edge if and only if v lies in uʼs sector and vice versa. In this paper we ask what is the smallest angle α for which there exists an integer , such that for any set P of n antennas of angle α and unbounded range, one can orient the antennas so that (i) the induced SCG is connected, and (ii) the union of the corresponding wedges is the entire plane. We show (by construction) that the answer to this question is , for which . Moreover, we prove that if and are two quadruplets of antennas of angle and unbounded range, separated by a line, to which one applies the above construction, independently, then the induced SCG of is connected. This latter result enables us to apply the construction locally, and to solve the following two further problems. In the first problem (replacing omni-directional antennas with directional antennas), we are given a connected unit disk graph, corresponding to a set P of omni-directional antennas of range 1, and the goal is to replace the omni-directional antennas by directional antennas of angle and range and to orient them, such that the induced SCG is connected, and, moreover, is an -spanner of the unit disk graph, w.r.t. hop distance. In our solution and the spanning ratio is 8. In the second problem (orientation and power assignment), we are given a set P of directional antennas of angle and adjustable range. The goal is to assign to each antenna p, an orientation and a range , such that the resulting SCG is (i) connected, and (ii) is minimized, where is a constant. For this problem, we devise an -approximation algorithm. [Copyright &y& Elsevier]

Abstract: In the Disk Multicover problem the input consists of a set P of n points in the plane, where each point has a covering requirement , and a set B of m base stations, where each base station has a weight . If a base station is assigned a radius , it covers all points in the disk of radius centered at b. The weight of a radii assignment is defined as , for some constant α. A feasible solution is an assignment such that each point p is covered by at least disks, and the goal is to find a minimum weight feasible solution. The Polygon Disk Multicover problem is a closely related problem, in which the set P is a polygon (possibly with holes), and the goal is to find a minimum weight radius assignment that covers each point in P at least K times. We present a -approximation algorithm for Disk Multicover, where is the maximum covering requirement of a point, and a -approximation algorithm for Polygon Disk Multicover. [Copyright &y& Elsevier]

Abstract: Let P be a set of n points in the plane in general position such that its elements are colored red or blue. We study the problem of finding two disjoint disks and such that covers only red points, covers only blue points, and the number of elements of P contained in is maximized. We prove that this problem can be solved in time. We also present a randomized algorithm that with high probability returns a -approximation to the optimal solution in time. [Copyright &y& Elsevier]

Abstract: For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of Pʼs vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of Set Cover and solved in time with a greedy -approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only cells, improving the running time of the algorithm to for simple polygons. In this paper we observe that, since minimum visibility decompositions for simple polygons have only sinks (i.e., cells of minimal visibility) (Bose et al., 2000), the running time of the algorithm can be further improved to . We then extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only cells and only cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of for simple polygons and for polygons with holes. [Copyright &y& Elsevier]

Abstract: We generalize the Euclidean 1-center approximation algorithm of Bădoiu and Clarkson (2003) to arbitrary Riemannian geometries, and study the corresponding convergence rate. We then show how to instantiate this generic algorithm to two particular settings: (1) the hyperbolic geometry, and (2) the Riemannian manifold of symmetric positive definite matrices. [Copyright &y& Elsevier]

Abstract: We present approximation algorithms for CF-coloring of points on a line with respect to a given set of intervals. For the restricted case where no two intervals have a common right endpoint, we present a 2-approximation algorithm, and, for the general case where intervals may share a right endpoint, we present a 4-approximation algorithm. The running time of both algorithms is . [Copyright &y& Elsevier]

Abstract: In this paper we study the following problem: Given sets R and B of r red and b blue points respectively in the plane, find a minimum-cardinality set of axis-aligned rectangles (boxes) so that every point in B is covered by at least one rectangle of , and no rectangle of contains a point of R. We prove the NP-hardness of the stated problem, and give either exact or approximate algorithms depending on the type of rectangles considered. If the covering boxes are vertical or horizontal strips we give an efficient algorithm that runs in time. For covering with oriented half-strips an optimal -time algorithm is shown. We prove that the problem remains NP-hard if the covering boxes are half-strips oriented in any of the four orientations, and show that there exists an -approximation algorithm. We also give an NP-hardness proof if the covering boxes are squares. In this situation, we show that there exists an -approximation algorithm. [Copyright &y& Elsevier]

Abstract: Inspired by air-traffic control and other applications where moving objects have to be labeled, we consider the following (static) point-labeling problem: given a set P of n points in the plane and labels that are unit squares, place a label with each point in P in such a way that the number of free labels (labels not intersecting any other label) is maximized. We develop efficient constant-factor approximation algorithms for this problem, as well as PTASs, for various label-placement models. [Copyright &y& Elsevier]

Abstract: We study a class of multi-commodity flow problems in geometric domains: For a given planar domain P populated with obstacles (holes) of types, compute a set of thick paths from a “source” edge of P to a “sink” edge of P for vehicles of K distinct classes. Each class k of vehicle has a given set, , of obstacles it must avoid and a certain width, , of path it requires. The problem is to determine if it is possible to route width- paths for class k vehicles from source to sink, with each path avoiding the requisite set of obstacles, and no two paths overlapping. This form of multi-commodity flow in two-dimensional domains arises in computing throughput capacity for multiple classes of aircraft in an airspace impacted by different types of constraints, such as those arising from weather hazards. We give both algorithmic theory results and experimental results. We show hardness of many versions of the problem by proving that two simple variants are NP-hard even in the case . If , then the problem is NP-hard even when . If , , then the problem is NP-hard even when . In contrast, the problem for a single width and a single type of obstacles is polynomially solvable. We present approximation algorithms for the multi-criteria optimization problems that arise when trying to maximize the number of routable paths. We also give a polynomial-time algorithm for the case in which the number of holes in the input domain is bounded. Finally, we give experimental results based on an implementation of our methods and experiment with enhanced heuristics for efficient solutions in practice. Our algorithms are being utilized in simulations with NASAʼs Future Air traffic management Concepts Evaluation Tool (FACET). We report on experimental results based on applying our algorithms to weather-impacted airspaces, comparing heuristic strategies for searching for feasible path orderings and for computing short multi-class routes. Our results show that multi-class routes can feasibly be computed on real weather data instances on the scale required in air traffic management applications. [Copyright &y& Elsevier]

Abstract: We consider the Minimum Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families where is connected for every pair of rectangles . This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of in general rectangle families, for any fixed , and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a novel way. [Copyright &y& Elsevier]

Abstract: We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879–895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh. [Copyright &y& Elsevier]

Abstract: Two complications frequently arise in real-world applications, motion and the contamination of data by outliers. We consider a fundamental clustering problem, the k-center problem, within the context of these two issues. We are given a finite point set S of size n and an integer k. In the standard k-center problem, the objective is to compute a set of k center points to minimize the maximum distance from any point of S to its closest center, or equivalently, the smallest radius such that S can be covered by k disks of this radius. In the discrete k-center problem the disk centers are drawn from the points of S, and in the absolute k-center problem the disk centers are unrestricted. We generalize this problem in two ways. First, we assume that points are in continuous motion, and the objective is to maintain a solution over time. Second, we assume that some given robustness parameter is given, and the objective is to compute the smallest radius such that there exist k disks of this radius that cover at least points of S. We present a kinetic data structure (in the KDS framework) that maintains a -approximation for the robust discrete k-center problem and a -approximation for the robust absolute k-center problem, both under the assumption that k is a constant. We also improve on a previous 8-approximation for the non-robust discrete kinetic k-center problem, for arbitrary k, and show that our data structure achieves a -approximation. All these results hold in any metric space of constant doubling dimension, which includes Euclidean space of constant dimension. [Copyright &y& Elsevier]

Abstract: The (Euclidean) Vehicle Routing Allocation Problem (VRAP) is a generalization of Euclidean TSP. We do not require that all points lie on the salesman tour. However, points that do not lie on the tour are allocated, i.e., they are directly connected to the nearest tour point, paying a higher (per-unit) cost. More formally, the input is a set of n points and functions and . We wish to compute a subset and a salesman tour π through T such that the total length of the tour plus the total allocation cost is minimum. The allocation cost for a single point is , where is the nearest point on the tour. We give a PTAS with complexity for this problem. Moreover, we propose an -time PTAS for the Steiner variant of this problem. This dramatically improves a recent result of Armon et al. [A. Armon, A. Avidor, O. Schwartz, Cooperative TSP, in: Proceedings of the 14th Annual European Symposium on Algorithms, 2006, pp. 40–51]. [Copyright &y& Elsevier]

Abstract: We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger''s Theorem. Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion. Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1. [Copyright &y& Elsevier]

Abstract: Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning—an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. We use a model for consistent dynamic labeling in which a label is represented by a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its active range, corresponding to the scales at which the label will be selected. The active range optimization (ARO) problem is to select active ranges so that no two truncated solids intersect and the sum of the heights of the active ranges is maximized. Simple ARO is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants. [Copyright &y& Elsevier]