2026-07-23T06:16:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7187 2024-03-06T10:40:04Z ddc:004 open_access

Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane Wang, Haitao rectilinear paths shortest paths minimum-link paths bicriteria paths rectilinear polygons Given a rectilinear domain 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 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 computing a minimum-link shortest s-t path, the previous algorithm runs in O(n log^{3/2} n) time while the time of our new algorithm is O(n + h log^{3/2} h). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.60 urn:nbn:de:0030-drops-71876 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.60 eng https://creativecommons.org/licenses/by/3.0/legalcode