Delaunay triangulation of imprecise points, preprocess and actually get a fast query time

We propose a new algorithm to preprocess a set of <em>n</em> disjoint unit disks in <em>O</em>(<em>n</em> log <em>n</em>) expected time, allowing to compute the Delaunay triangulation of a set of <em>n</em> points, one from each disk, in <em>O</em>(<em>n</em>) 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.

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.