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 [1], which is based on independent sets, our algorithm uses a breadth rst 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 signi cantly 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 1 of the points, even if we restrict the degree 3 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 di erences between two consecutive vertices of the given order.