An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
复制标题
简单多边形测地最远点Voronoi图的最优确定性算法
DOI：
10.1007/s00454-022-00424-6
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Wang, Haitao
中科院分区：
文献类型：
--
作者：
Wang, Haitao
给定平面上简单多边形 Pofn 顶点中的一组 Sofm 点位置，我们考虑计算 SinP 的测地线最远点 Voronoi 图的问题。众所周知，该问题具有反时间下界。此前，提出了一种随机算法 [Barba, SoCG 2019]，可以意外地解决问题。以前最好的确定性算法可以及时解决问题 [Oh, Barba, and Ahn, SoCG 2016] 或及时 [Oh and Ahn, SoCG 2017]。在本文中，我们提出了一种需要时间的确定性算法，这是最优的。这肯定地回答了米切尔二十年前在《计算几何手册》中提出的一个悬而未决的问题。
Given in the plane a setSofmpoint sites in a simple polygonPofnvertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram forSinP. It is known that the problem has antime lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that solves the problem inexpected time. The previous best deterministic algorithms solve the problem intime [Oh, Barba, and Ahn, SoCG 2016] or intime [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm that takestime, which is optimal. This answers affirmatively an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
登录
查看更多内容
计算简单多边形中的测地线最远邻居
DOI：
10.1016/0022-0000(89)90045-7
发表时间：
1989
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
S. Suri
通讯作者：
S. Suri
简单多边形点测地线Voronoi图的近乎最优算法
影响因子：
1.1
作者：
Chih
通讯作者：
Chih
使用测地线三角测量在多边形中进行射线射击
影响因子：
1.1
作者：
B. Chazelle;H. Edelsbrunner;Michelangelo Grigni;L. Guibas;J. Hershberger;M. Sharir;J. Snoeyink
通讯作者：
J. Snoeyink
简单多边形中中等大小点集的 Voronoi 图
影响因子：
0.8
作者：
Eunjin Oh;Hee
通讯作者：
Hee
关于凸包的 Omega(n log n) 下界和最大向量确定
DOI：
10.1016/0020-0190(80)90064-2
发表时间：
1980
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
P. Boas
通讯作者：
P. Boas