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

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download


https://hal.inria.fr/inria-00595823
Contributor : Olivier Devillers <>
Submitted on : Wednesday, May 25, 2011 - 4:10:13 PM
Last modification on : Saturday, January 27, 2018 - 1:30:42 AM
Long-term archiving on : Friday, August 26, 2011 - 2:27:02 AM

Files

41-226-1-PB.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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

Share

Metrics

Record views

300

Files downloads

289