On Properties of Higher-Order Delaunay Graphs with Applications ∗
Manuel Abellanas, Prosenjit K. Bose, Jesús García-López, Ferrán Hurtado, Mariano Nicolás, Pedro A. Ramos · 2005
In this work we study the order-k Delaunay graph, which is formed by edges pq having a circle through p and q and containing no more than k sites. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph and show that it is connected under the flip operation if k ≤ 1andforeveryk if points are in convex position. We also study the hamiltonicity of the order-k Delaunay graph and give an application to a coloring problem.