Higher order Delaunay triangulations (Q1614071)

The authors introduce a \(k-\)OD triangulation in terms of some given number \(k\) of points. This generalizes the well known Delaunay triangulation [see \textit{L. P. Chew}, Algorithmica 4, No.~1, 97-108 (1989; Zbl 0664.68042)]. An efficient way to compute all useful \(k-\)OD edges of a point set is given. An algorithm to compute which edges can be included in a \(k-\)OD triangulation is also given. The class of 1-OD triangulation is examined in more detail. Applications are also indicated which include realistic terrain modeling and mesh generation.