$L_1$ Shortest Path Queries in Simple Polygons

Sang Won Bae, Haitao Wang

Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L_1$ shortest path queries in $P$. We build a data structure of $O(n)$ size in $O(n)$ time such that given any t…