Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Wednesday, August 8, 2007 - 7:10:52 PM
Last modification on : Friday, February 4, 2022 - 3:10:49 AM
Long-term archiving on: : Thursday, April 8, 2010 - 7:12:45 PM


Files produced by the author(s)




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⟩



Record views


Files downloads