2019/03/04 by Wang, Haitao
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1903.01417
Let P be a polygonal domain of h holes and n vertices. We study the problem of constructing a data structure that can compute a shortest path between s and t in P under the L1 metric for any two query points s and t. To do so, a standard approach is to first find a set of ns "gateways" for s and a set of nt "gateways" for t such that there exist a shortest s-t path containing a gateway of s and a gateway of t, and then compute a shortest s-t path using these gateways. Previous algorithms all take quadratic O(ns⋅ nt) time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in O(ns + nt log ns) time. As a consequence, we construct a data structure of O(n+(h2log3 h/loglog h)) size in O(n+(h2log4 h/loglog h)) time such that each query can be answered in O(log n) time.