# Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane

Preprint · Haitao Wang

- Archive id: arxiv:1703.04466
- Published: 2017-03-13
- arXiv: https://arxiv.org/abs/1703.04466
- Source URL: https://arxiv.org/abs/1703.04466
- PDF: https://arxiv.org/pdf/1703.04466
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.