A dynamic hierarchical subdivision algorithm for computing Delaunay triangulations and other closest-point problems

Publisher Website
Google Scholar
Abstract
A new, dynamic, hierarchical subdivision and recursive algorithm for computing Delaunay triangulations is presented. The algorithm has four main steps: (1) location of the already formed triangle that contains the point (2) identification of other adjoining triangles whose circumcircle contains the point (3) formation of the new triangles, and (4) database update. Different search procedures are analyzed. It is shown that the “oriented walk” search, when the total number of points is less than 417 or when the points are presorted by distance or coordinates. The algorithm has point-deletion capabilities which are discussed in detail.

This publication has 17 references indexed in Scilit: