A Linear-Time Approximation Scheme for Minimum Weight Triangulation of Convex Polygons

A linear-time heuristic for minimum weight triangulation of convex polygons is presented. This heuristic produces a triangulation of length within a factor 1 + ε from the optimum, where ε is an arbitrarily small positive constant. This is the first subcubic algorithm that guarantees such an approximation factor, and it has interesting applications. Received November 21, 1996; revised March 9, 1997.     

A note on a QPTAS for maximum weight triangulation of planar point sets

We observe that the recent quasi-polynomial time approximation scheme (QPTAS) of Adamaszek and Wiese for the Maximum Weight Independent Set of Polygons problem, where polygons have at most a polylogarithmic number of vertices and nonnegative weights, yields:

1.

a QPTAS for the problem of finding, for a set S of n points in the plane, a planar straight-line graph (PSLG) whose vertices are the points in S and whose each interior face is a simple polygon with at most a polylogarithmic in n number of vertices such that the total weight of the inner faces is maximized, and in particular,     

A balanced search tree with O(1) worst-case update time

Summary In this paper a new data structure is described for performing member and neighbor queries in O(logn) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or O(log^* n) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's Ω(n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).     

Sublinear merging and natural mergesort

The complexity of merging two sorted sequences into one is linear in the worst case as well as in the average case. There are, however, instances for which a sublinear number of comparisons is sufficient. We consider the problem of measuring and exploiting such instance easiness. The merging algorithm presented, Adaptmerge, is shown to adapt optimally to different kinds of measures of instance easiness. In the sorting problem the concept of instance easiness has received a lot of attention, and it is interpreted by a measure of presortedness. We apply Adaptmerge in the already adaptive sorting algorithm Natural Mergesort. The resulting algorithm, Adaptive Mergesort, optimally adapts to several, known and new, measures of presortedness. We also prove some interesting results concerning the relation between measures of presortedness proposed in the literature.     

There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)[2π/3 cos(π/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)[2/3 cos(/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short'' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.