Fast reconstruction of Delaunay triangulations

摘要

We present a new linear time algorithm to compute a good order for the point set of a Delaunay triangulation in the plane. Such a good order makes reconstruction in linear time with a simple algorithm possible. Similarly to the algorithm of Snoeyink and van Kreveld [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-47 1], our algorithm constructs such orders in O(log n) phases by repeatedly removing a constant fraction of vertices from the current triangulation. Compared to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471] we improve the guarantee on the number of removed vertices in each such phase. If we restrict the degree of the points (at the time they are removed) to 6, our algorithm removes at least 1/3 of the points while the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 45947 1] gives a guarantee of 1/10. We achieve this improvement by removing the points sequentially using a breadth first search (BFS) based procedure that-in contrast to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-47 I]-does not (necessarily) remove an independent set.Besides speeding up the algorithm, removing more points in a single phase has the advantage that two consecutive points in the computed order are usually closer to each other. For this reason, we believe that our approach is better suited for vertex coordinate compression.We implemented prototypes of both algorithms and compared their running time on point sets uniformly distributed in the unit cube. Our algorithm is slightly faster. To compare the vertex coordinate compression capabilities of both algorithms we round the resulting sequences of vertex coordinates to 16-bit integers and compress them with a simple variable length code. Our algorithm achieves about 14% better vertex data compression than the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-47 1]. (c) 2005 Elsevier B.V. All rights reserved.