  Given a rectilinear domain $\mathcal{P}$ of $h$ pairwise-disjoint rectilinear
obstacles with a total of $n$ vertices in the plane, we study the problem of
computing bicriteria rectilinear shortest paths between two points $s$ and $t$
in $\mathcal{P}$. Three types of bicriteria rectilinear paths are considered:
minimum-link shortest paths, shortest minimum-link paths, and minimum-cost
paths where the cost of a path is a non-decreasing function of both the number
of edges and the length of the path. The one-point and two-point path queries
are also considered. Algorithms for these problems have been given previously.
Our contributions are threefold. First, we find a critical error in all
previous algorithms. Second, we correct the error in a not-so-trivial way.
Third, we further improve the algorithms so that they are even faster than the
previous (incorrect) algorithms when $h$ is relatively small. For example, for
the minimum-link shortest paths, we obtain the following results. Our algorithm
computes a minimum-link shortest $s$-$t$ path in $O(n+h\log^{3/2} h)$ time. For
the one-point queries, we build a data structure of size $O(n+ h\log h)$ in
$O(n+h\log^{3/2} h)$ time for a source point $s$, such that given any query
point $t$, a minimum-link shortest $s$-$t$ path can be determined in $O(\log
n)$ time. For the two-point queries, with $O(n+h^2\log^2 h)$ time and space
preprocessing, a minimum-link shortest $s$-$t$ path can be determined in
$O(\log n+\log^2 h)$ time for any two query points $s$ and $t$; alternatively,
with $O(n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}})$ time and $O(n+h^2\cdot
\log h \cdot 4^{\sqrt{\log h}})$ space preprocessing, we can answer each
two-point query in $O(\log n)$ time.
