AbstractIn this paper we show a parallel algorithm that produces a triangulation which is within a constant factor longer than the Minimum Weight Triangulation (MWT) in time O(log n) using O(n) processors and linear space in the CRCW PRAM model. We present a relaxed version of the quasi-greedy triangulation algorithm which produces edges which are at most (1+epsilon) longer than the shortest diagonal, where epsilon is some positive constant smaller than 1. The analysis shows that the relaxed version still outputs a triangulation which is within a constant factor longer than the minimum weight triangulation. We also show that the approximation behavior of the greedy algorithm may deteriorate dramatically, i.e. Omega(n) longer than a minimum weight triangulation, if the lengths of the edges are not computed with high precision.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: computational geometry, approximation algorithms, triangulation
Selected references
- David G. Kirkpatrick. A note on Delaunay and optimal triangulations. Information Processing Letters, 10(3):127-128, 18 April 1980.
- D. T. Lee and F. P. Preparata. The all nearest-neighbor problem for convex polygons. Information Processing Letters, 7(4):189-192, June 1978.
- Christos Levcopoulos. An Omega(sqrt(n)) lower bound for the nonoptimality of the greedy triangulation. Information Processing Letters, 25(4):247-251, 17 June 1987.
- Christos Levcopoulos and Drago Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. Journal of Algorithms, 27(2):303-338, May 1998.
- Christos Levcopoulos and Andrzej Lingas. On approximation behavior of the greedy triangulation for convex polygons. Algorithmica, 2:15-193, 1987.
- Cao An Wang and Yung H. Tsin. An O(log n) time parallel algorithm for triangulating a set of points in the plane. Information Processing Letters, 25(1):55-60, 20 April 1987.