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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00485915
Contributor : Olivier Devillers <>
Submitted on : Friday, May 28, 2010 - 11:15:23 AM
Last modification on : Saturday, January 27, 2018 - 1:30:56 AM
Long-term archiving on: Thursday, December 1, 2016 - 4:02:37 AM

File

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

Identifiers

  • HAL Id : inria-00485915, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

294

Files downloads

130