The hierarchical representation of objects: the Delaunay tree

ABSTRACT

We present, in this paper, a new hierarchical data structure called the Delaunay tree. It is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy of balls. The Delaunay tree provides efficient solutions to several problems such as building the Delaunay triangulation of a finite set of n points in any dimension, locating a point in the triangulation, defining neighborhood relationships in the triangulation and computing intersections. The algorithms are extremely simple and are analyzed from a theoretical and practical points of view.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations; Curve, surface, solid, and object representations

General Terms:
Algorithms, Experimentation, Theory, Verification