The Delaunay Hierarchy

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and the possibility of fully dynamic insertions and deletions. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the level below. Point location is done by walking in a triangulation to determine the nearest neighbor of the query at that level, then the walk restarts from that neighbor at the level below. Using a small subset (3%) to sample a level allows a small memory occupation; the walk and the use of the nearest neighbor to change levels quickly locate the query.
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00166711
Contributor : Olivier Devillers <>
Submitted on : Wednesday, August 8, 2007 - 7:10:52 PM
Last modification on : Wednesday, March 7, 2018 - 10:33:37 AM
Long-term archiving on : Thursday, April 8, 2010 - 7:12:45 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Devillers. The Delaunay Hierarchy. International Journal of Foundations of Computer Science, World Scientific Publishing, 2002, 13, pp.163-180. ⟨10.1142/S0129054102001035⟩. ⟨inria-00166711⟩

Share

Metrics

Record views

644

Files downloads

1199