Fast Reconstruction of Delaunay Triangulations

We present a new ( O(n) ) algorithm to compute good orders for the point set of a Delaunay triangulation of ( n ) points in the plane. Such a good order makes reconstruction in ( O(n) ) time with a simple algorithm possible. In contrast to the algorithm of Snoeyink and van Kreveld cite1, which is based on independent sets, our algorithm uses a breadth first search (BFS) to obtain these orders. Both approaches construct such orders by repeatedly removing a constant fraction of vertices from the current triangulation. The advantage of the BFS approach is that we can give significantly better bounds on the fraction of removed points in a phase of the algorithm. We can prove that a single phase of our algorithm removes at least ( frac13 ) of the points, even if we restrict the degree of the points (at the time they are removed) to 6. We implemented and compared both algorithms. Our algorithms is slightly faster and achieves about 15% better vertex data compression when using a simple variable length code to encode the differences between two consecutive vertices of the given order.