  We devise a data structure that can answer shortest path queries for two
query points in a polygonal domain $P$ on $n$ vertices. For any $\varepsilon >
0$, the space complexity of the data structure is $O(n^{10+\varepsilon })$ and
queries can be answered in $O(\log n)$ time. Alternatively, we can achieve a
space complexity of $O(n^{9+\varepsilon })$ by relaxing the query time to
$O(\log^2 n)$. This is the first improvement upon a conference paper by Chiang
and Mitchell from 1999. They present a data structure with $O(n^{11})$ space
complexity and $O(\log n)$ query time. Our main result can be extended to
include a space-time trade-off. Specifically, we devise data structures with
$O(n^{9+\varepsilon}/\hspace{1pt} \ell^{4 + O(\varepsilon )})$ space complexity
and $O(\ell \log^2 n )$ query time, for any integer $1 \leq \ell \leq n$.
  Furthermore, we present improved data structures with $O(\log n)$ query time
for the special case where we restrict one (or both) of the query points to lie
on the boundary of $P$. When one of the query points is restricted to lie on
the boundary, and the other query point is unrestricted, the space complexity
becomes $O(n^{6+\varepsilon})$. When both query points are on the boundary, the
space complexity is decreased further to $O(n^{4+\varepsilon })$, thereby
improving an earlier result of Bae and Okamoto.
