Constrained higher order Delaunay triangulations

We extend the notion of higher-order Delaunay triangulations to constrained higher-order Delaunay triangulations and provide various results. We can determine the order k of a given triangulation in O(min(nklognlogk,n3/2logO(1)n)) time. We show that the completion of a set of useful order-k Delaunay edges may have order 2k−2, which is worst-case optimal. We give an algorithm for the lowest-order completion for a set of useful order-k Delaunay edges when k⩽3. For higher orders the problem is open.