Higher order Delaunay triangulations

Abstract

For a set P of points in the plane, we introduce a class of triangulations that is an extension of the Delaunay triangulation. Instead of requiring that for each triangle the circle through its vertices contains no points of P inside, we require that at most k points are inside the circle. Since there are many different higher-order Delaunay triangulations for a point set, other useful criteria for triangulations can be incorporated without sacrificing the well-shapedness too much. Applications include realistic terrain modelling and mesh generation.