  Let $\mathcal{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 $\mathcal{P}$ under the $L_1$ metric for any two
query points $s$ and $t$. To do so, a standard approach is to first find a set
of $n_s$ "gateways" for $s$ and a set of $n_t$ "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(n_s\cdot n_t)$ time to solve this problem. In
this paper, we propose a divide-and-conquer technique that solves the problem
in $O(n_s + n_t \log n_s)$ time. As a consequence, we construct a data
structure of $O(n+(h^2\log^3 h/\log\log h))$ size in $O(n+(h^2\log^4 h/\log\log
h))$ time such that each query can be answered in $O(\log n)$ time.
