Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2010

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

(1)
1
Olivier Devillers

Abstract

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).
Fichier principal
Vignette du fichier
RR-7299.pdf (461.5 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00485915 , version 1 (23-05-2010)
inria-00485915 , version 2 (28-05-2010)

Identifiers

  • HAL Id : inria-00485915 , version 2

Cite

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⟩
110 View
98 Download

Share

Gmail Facebook Twitter LinkedIn More