Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane

DOI10.4230/LIPICS.SOCG.2017.60MaRDI QIDQ4580138zbMATH OpenOpenAlexFDO

Authors Haitao Wang

Publication date 13 August 2018

Full work available at URL https://arxiv.org/abs/1703.04466

zbMATH Keywords

shortest pathsrectilinear pathsrectilinear polygonsminimum-link pathsbicriteria paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given a rectilinear domain $mathcalP$ 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 $mathcalP$. 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+hlo{g}^{3/2}h)$ time. For the one-point queries, we build a data structure of size $O(n+hlogh)$ in $O(n+hlo{g}^{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(logn)$ time. For the two-point queries, with $O(n+h^{2}lo{g}^{2}h)$ time and space preprocessing, a minimum-link shortest $s$-$t$ path can be determined in $O(logn+lo{g}^{2}h)$ time for any two query points $s$ and $t$; alternatively, with $O(n+h^{2}cdotlo{g}^{2}hcdot{4}^{sqrtlogh})$ time and $O(n+h^{2}cdotloghcdot{4}^{sqrtlogh})$ space preprocessing, we can answer each two-point query in $O(logn)$ time.

Recommendations

• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Minimum-link shortest paths for polygons amidst rectilinear obstacles
• Rectilinear Path Problems among Rectilinear Obstacles Revisited

Cited in

(3)

• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Computing shortest paths in the plane with removable obstacles
• Reachable region query and its applications

This page was built for publication: Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580138)