Skip to Main content Skip to Navigation
Reports

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 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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00485915
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Sunday, May 23, 2010 - 11:48:22 AM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Friday, October 19, 2012 - 3:00:43 PM

File

RR-7299.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00485915, version 1

Citation

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

Share

Metrics

Record views

106

Files downloads

93