Fast reconstruction of Delaunay triangulations

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-471].