A Parallel Approximation Algorithm for Minimum Weight Triangulation

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(logn) using O(n) processors and linear space in the CRCW PRAM model. This is done by developing a relaxed version of the quasi-greedy triangulation algorithm. The relaxed version produces edges that are at most (1+ε) longer than the shortest diagonal, where ε is some positive constant smaller than 1, still outputs a triangulation which is within a constant factor longer that the minimum weight triangulation. However, if the same method is applied to the straight-forward greedy algorithm the approximation behavior may deteriorate dramatically, i.e. Ω(n) longer than a minimum weight triangulation, if the lengths of the edges are not computed with high precision.