On properties of higher-order Delaunay graphs with applications
On properties of higher-order Delaunay graphs with applications
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Abellanas;P. Bose;J. García-López;F. Hurtado;M. Nicolás;P. Ramos
中科院分区：
文献类型：
--
作者：
M. Abellanas;P. Bose;J. García-López;F. Hurtado;M. Nicolás;P. Ramos
在这项工作中，我们研究了 k 阶 Delaunay 图，它由具有穿过 p 和 q 的圆的边 pq 形成，并且包含不超过 k 个位置。我们研究了可以用该图的边构造的三角剖分集的组合结构，并表明如果 k ≤ 1a 且对于每个 k 如果点位于凸位置，则它在翻转操作下是连通的。我们还研究了 k 阶 Delaunay 图的哈密顿性并给出了在着色问题上的应用。
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 ≤ 1a nd for everyk 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.