Delaunay triangulation of imprecise points, preprocess and actually get a fast query time
Olivier Devillers · Journal of Computational Geometry (Carleton University) · 2010
We propose a new algorithm to preprocess a set of n disjoint unit disks in O(n log n) expected time, allowing to compute the Delaunay triangulation of a set of n points, one from each disk, in O(n) expected time. Our algorithm has the same asymptotic complexity as previous ones for this problem, but our algorithm is much simpler and it runs faster in practice than a direct computation of the Delaunay triangulation.