Two-Point $L_1$ Shortest Path Queries in the Plane

Danny Z. Chen, Rajasekhar Inkulu, Haitao Wang

Let $\mathcal{P}$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can qui…