2018/09/20 by Sang Won Bae, Haitao Wang, Bae, Sang Won +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1809.07481
openalex publication_date 2018/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.