C G ] 2 0 Se p 20 18 L 1 Shortest Path Queries in Simple Polygons
C G ] 2 0 Se p 20 18 L 1 Shortest Path Queries in Simple Polygons
复制标题
C G ] 2 0 Sep 20 18 L 1 简单多边形中的最短路径查询
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Haitao Wang
中科院分区：
文献类型：
--
作者：
S. Bae;Haitao Wang
设P是n个顶点的简单多边形。我们考虑P中两点L1最短路径查询。我们在O（n）时间内建立了一个O（n）大小的数据结构，使得给定任意两个查询点s和t，P中从s到t的L1最短路径的长度可以在O（log n）时间内计算，或者如果s和t都是P的顶点，则在O（1）时间内计算，并且实际最短路径可以在额外的线性时间内输出路径的边数。为了实现这个结果，我们提出了一个简单多边形的山分解，它本身可能是有趣的。最重要的是，我们的方法比以前在这个问题上的工作要简单得多。
Let P be a simple polygon of n vertices. We consider two-point L1 shortest path queries in P . We build a data structure of O(n) size in O(n) time such that given any two query points s and t, the length of an L1 shortest path from s to t in P can be computed in O(log n) time, or in O(1) time if both s and t are vertices of P , and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.