Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time

Olivier Devillers (1)

1 GEOMETRICA - Geometric computing

We propose a new algorithm that preprocess a set of n disjoint unit disks to be able to compute the Delaunay triangulation in O(n) expected time. Conversely to previous similar results, our algorithm is actually faster than a direct computation in O(n log n) time.

Nous proposons un algorithme qui prétraite un ensemble de disques unitaires disjoints pour être capable de calculer la triangulation d'un ensemble de n points, un dans chaque disque, en temps moyen O(n). Par rapport à d'autres résultats simiaires, notre algorithme permet également d'avoir effectivement un temps de calcul meilleur que les algorithmes classiques en O(n log n).

Domaines: Géométrie algorithmique [cs.CG]

Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. [Research Report] RR-7299, INRIA. 2010, pp.10. ⟨inria-00485915v2⟩