Approximation algorithms for terrain guarding

We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a Minimum Set Cover instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of O(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions.     

Efficiently determining a locally exact shortest path on polyhedral surfaces

In this paper, we present an efficient visibility-based algorithm for determining a locally exact shortest path (LESP) from a source point to a destination point on a (triangulated) polyhedral surface. Our algorithm, of a finitely-iterative scheme, evolves an initial approximately shortest path into a LESP. During each iteration, we first compute the exact shortest path restricted on the current face sequence according to Fermat’s principle which affirms that light always follows the shortest optical path, and then optimize the face sequence where the path is not locally shortest on the polyhedral surface. Since the series of paths we obtained are monotonic decreasing in length, the algorithm gives a LESP which is shorter than the initial path, at conclusion.

For comparison, we use various methods to provide an initial path. One of the methods is Dijkstra’s algorithm, and the others are the Fast Marching Method (FMM) and its improved version. Our intention for improvement is to overcome the limitation of acute triangulations in the original version. To achieve this goal, we classify all the edges into seven types according to different wavefront propagation manners, and dynamically determine the type of each edge for controlling the subsequent wavefront expansion. Furthermore, we give two approaches for backtracing the approximately shortest paths directed at the improved FMM. One exploits the known propagation manners of the edges as well as the Euler’s method. This is another contribution in this paper.     

On discretization methods for approximating optimal paths in regions with direction-dependent costs

The optimal path planning problems are very difficult in the case where the cost metric varies not only in different regions of the space, but also in different directions inside the same region. If the classic discretization approach is adopted to compute an ?-approximation of the optimal path, the size of the discretization (and thus the complexity of the approximation algorithm) is usually dictated by a number of geometric parameters and thus can be very large. In this paper we show a general method for choosing the variables of the discretization to maximally reduce the dependency of the size of the discretization on various geometric parameters. We use this method to improve the previously reported results on two optimal path problems with direction-dependent cost metrics.     

Approximation Algorithms for a k-Line Center

Given a set P of n points in ℝd and an integer k ≥ 1, let w^* denote the minimum value so that P can be covered by k congruent cylinders of radius w^*. We describe a randomized algorithm that, given P and an ε > 0, computes k cylinders of radius (1 + ε) w^* that cover P. The expected running time of the algorithm is O(n log n), with the constant of proportionality depending on k, d, and ε. We first show that there exists a small ”certificate” Q ⫅ P, whose size does not depend on n, such that for any k congruent cylinders that cover Q, an expansion of these cylinders by a factor of (1 + ε) covers P. We then use a well-known scheme based on sampling and iterated re-weighting for computing the cylinders.     

Shortest paths in simple polygons with polygon-meet constraints

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons.     

The convex hull of a regular set of integer vectors is polyhedral and effectively computable

Number Decision Diagrams (NDD) provide a natural finite symbolic representation for regular set of integer vectors encoded as strings of digit vectors (least or most significant digit first). The convex hull of the set of vectors represented by a NDD is proved to be an effectively computable convex polyhedron.     

Algorithms for bichromatic line-segment problems and polyhedral terrains

We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.Work on this paper by the first author has been supported in part by the National Science Foundation under Grant CCR-9002352. Work by the second author was supported in part by the National Science Foundation under Grant CCR-8714565. The fourth author has been supported in part by the Office of Naval Research under Grant N0014-87-K-0129, by the National Science Foundation under Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a grant from the US-Israeli Binational Science Foundation.     

Well-separated pair decomposition in linear time?

Given a point set in a fixed dimension, we note that a well-separated pair decomposition can be found in linear time if we assume that the ratio of the farthest pair distance to the closest pair distance is polynomially bounded. Many consequences follow; for example, we can construct spanners or solve the all-nearest-neighbors problem in linear time (under the same assumption), and we compute an approximate Euclidean minimum spanning tree in linear time (without any assumption).     

Classification of the Dubins set

Given two points in a plane, each with a prescribed direction of motion in it, the question being asked is to find the shortest smooth path of bounded curvature that joins them. The classical 1957 result by Dubins gives a sufficient set of paths (each consisting of circular arcs and straight line segments) which always contains the shortest path. The latter is then found by explicitly computing all paths on the list and then comparing them. This may become a problem in applications where computation time is critical, such as in real-time robot motion planning. Instead, the logical classification scheme considered in this work allows one to extract the shortest path from the Dubins set directly, without explicitly calculating the candidate paths. The approach is demonstrated on one of two possible cases that appear here — when the distance between the two points is relatively large (the case with short distances can be treated similarly). Besides computational savings, this result sheds light on the nature of factors affecting the length of paths in the Dubins problem, and is useful for further extensions, e.g. for finding the shortest path between a point and a manifold in the corresponding configuration space.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

An approximative solution to the Zookeeper's Problem

Consider a simple polygon P containing disjoint convex polygons each of which shares an edge with P. The Zookeeper's Problem then asks for the shortest route in P that visits all convex polygons without entering their interiors. Existing algorithms that solve this problem run in time super-linear in the size of P and the convex polygons. They also suffer from numerical problems.In this paper, we shed more light on the problem and present a simple linear time algorithm for computing an approximate solution. The algorithm mainly computes shortest paths and intersections between lines using basic data structures. It does not suffer from numerical problems. We prove that the computed approximation route is at most 6 times longer than the shortest route in the exact solution.     

Near-Linear Time Approximation Algorithms for Curve Simplification

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P’ whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ² in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L_p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.     

Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

On the approximability of two tree drawing conventions

We consider two aesthetic criteria for the visualization of rooted trees: inclusion and tip-over. Finding the minimum area layout according to either of these two standards is an NP-hard task, even when we restrict ourselves to binary trees.We provide a fully polynomial time approximation scheme for this problem. This result applies to any tree for tip-over layouts and to bounded degree trees in the case of the inclusion convention. We also prove that such restriction is necessary since, for unbounded degree trees, the inclusion problem is strongly NP-hard. Hence, neither a fully polynomial time approximation scheme nor a pseudopolynomial time algorithm exists, unless P=NP. Our technique, combined with the parallel algorithm by Metaxas et al. [Comput. Geom. 9 (1998) 145-158], also yields an NC fully parallel approximation scheme. This latter result holds for inclusion of binary trees and for the slicing floorplanning problem. Although this problem is in P, it is unknown whether it belongs to NC or not. All the above results also apply to other size functions of the drawing (e.g., the perimeter).     

A fast deterministic smallest enclosing disk approximation algorithm

We describe a simple and fast -time algorithm for finding a (1+?)-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented.     

An improved FPTAS for Restricted Shortest Path

Given a graph with a cost and a delay on each edge, Restricted Shortest Path (RSP) aims to find a min-cost s-t path subject to an end-to-end delay constraint. The problem is NP-hard. In this note we present an FPTAS with an improved running time of O(mn/ε) for acyclic graphs, where m and n denote the number of edges and nodes in the graph. Our algorithm uses a scaling and rounding technique similar to that of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42]. The novelty of our algorithm lies in its “adaptivity”. During each iteration of our algorithm the approximation parameters are fine-tuned according to the quality of the current solution so that the running time is kept low while progress is guaranteed at each iteration. Our result improves those of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42], Phillips [Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 776-785], and Raz and Lorenz [Technical Report, 1999].     

Hitting sets when the VC-dimension is small

We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm uses a linear programming relaxation to compute a probability measure for which ?-nets are always hitting sets (see Corollary 15.6 in Pach and Agarwal [Combinatorial Geometry, J. Wiley, New York, 1995]). The comparable algorithm of Brönnimann and Goodrich [Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995) 463] computes such a probability measure by an iterative reweighting technique. The running time of our algorithm is comparable with theirs, and the approximation ratio is smaller by a constant factor. We also show how our algorithm can be parallelized and extended to the minimum cost hitting set problem.