Computing the L1 geodesic diameter and center of a polygonal domain
Computing the L1 geodesic diameter and center of a polygonal domain
复制标题
计算多边形域的 L1 测地线直径和中心
DOI：
10.1007/s00454-016-9841-z
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
2016
中科院分区：
文献类型：
--
作者：
S. W. Bae;M. Korman;J. S. B. Mitchell;Y. Okamoto;V. Polishchuk;and H. Wang. . ;pages 1-28;2016
对于具有h个孔洞和n个顶点的多边形区域，我们给出了分别计算时间上测地线直径和时间上测地线中心的算法，其中表示逆Ackermann函数。以前没有已知的算法来解决这些问题。对于欧氏映射，最好的算法是实时计算测地线直径，实时计算测地线中心。因此，我们的算法是显着快于欧几里德问题的算法。我们的算法是基于几个有趣的观察最短路径在多边形域。
For a polygonal domain withhholes and a total ofnvertices, we present algorithms that compute thegeodesic diameter intime and thegeodesic center intime, respectively, wheredenotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter inortime, and compute the geodesic center intime. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations onshortest paths in polygonal domains.