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 the 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.
