The Delaunay hierarchy, a structure to compute the Delaunay triangulation

The Delaunay hierarchy is a new data structure to compute the Delaunay triangulation of a set of points in the plane. It allows to combine: a good worst case complexity, a very fast behavior on real data and a small memory occupation. It also allows dynamic updates (insertions and deletions)

The location structure is structured in several levels. The lowest level just consists in the triangulation, then each level contain the triangulation of a small sample of the levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restart from that neighbor at the level below. Using a small sample (3 \%) allows a small memory occupation; the march and the use of the nearest neighbor to change permit to locate quickly the query.

The deletion is implemented by duality with the convex hull in 3D using a partial shelling.

This work is currently available in CGAL
Last modified: Tue Jan 17 11:08:28 CET 2006 Olivier Devillers Software PRISME Homepage la même page en français