Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time - Archive ouverte HAL Access content directly
Journal Articles Journal of Computational Geometry Year : 2011

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

(1)
1
Olivier Devillers

Abstract

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.
Fichier principal
Vignette du fichier
41-226-1-PB.pdf (561.16 Ko) Télécharger le fichier
Vignette du fichier
vignette-inria-00595823.jpg (1.44 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Format : Figure, Image
Loading...

Dates and versions

inria-00595823 , version 1 (25-05-2011)

Identifiers

Cite

Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. Journal of Computational Geometry, 2011, 2 (1), pp.30-45. ⟨10.20382/jocg.v2i1a3⟩. ⟨inria-00595823⟩
151 View
263 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More