Two-Point L1 Shortest Path Queries in the Plane
Two-Point L1 Shortest Path Queries in the Plane
Let P be a set of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane. In this paper, we consider the problem of building a data structure that can quickly compute an L1 shortest obstacle-avoiding path between any two query points s and t. We build …