Computing L1 Shortest Paths Among Polygonal Obstacles in the Plane

作     者：Chen, Danny Z. Wang, Haitao 

作者机构：Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA Utah State Univ Dept Comp Sci Logan UT 84322 USA 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2019年第81卷第6期

页      面：2430-2483页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CCF-1317143] 

主　　题：Shortest paths Polygonal domains L1 metric Voronoi diagrams Computational geometry Algorithms and data structures 

摘      要：Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given;we present an O(n+hlogh) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of an L1 shortest obstacle-avoiding path from s to t can be computed in O(logn) time and the actual path can be reported in additional time proportional to the number of edges of the path. The previously best algorithm computes such a shortest path map in O(nlogn) time and O(n) space. So our algorithm is faster when h is relatively small. Further, our techniques can be extended to obtain improved results for other related problems, e.g., computing the L1 geodesic Voronoi diagram for a set of point sites among the obstacles.