Document Open Access Logo

Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane

Author Haitao Wang

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2017.60.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • rectilinear paths
  • shortest paths
  • minimum-link paths
  • bicriteria paths
  • rectilinear polygons

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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).

Cite As Get BibTex

Haitao Wang. Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.60

Author Details

Haitao Wang

References

  1. R. Bar-Yehuda and B. Chazelle. Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications, 4(4):475-481, 1994. Google Scholar
  2. D. Z. Chen, O. Daescu, and K. S. Klenk. On geometric path query problems. International Journal of Computational Geometry and Applications, 11(6):617-645, 2001. Google Scholar
  3. D. Z. Chen, R. Inkulu, and H. Wang. Two-point L₁ shortest path queries in the plane. In Proc. of the 30th Annual Symposium on Computational Geometry, pages 406-415, 2014. Google Scholar
  4. D. Z. Chen, K. S. Klenk, and H.-Y. T. Tu. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing, 29(4):1223-1246, 2000. Google Scholar
  5. D. Z. Chen and H. Wang. A nearly optimal algorithm for finding L₁ shortest paths among polygonal obstacles in the plane. In Proc. of the 19th European Symposium on Algorithms, pages 481-492, 2011. Google Scholar
  6. D. Z. Chen and H. Wang. L₁ shortest path queries among polygonal obstacles in the plane. In Proc. of 30th Symp. on Theoretical Aspects of Computer Science, pages 293-304, 2013. Google Scholar
  7. K. Clarkson, S. Kapoor, and P. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log² n) time. In Proc. of the 3rd Annual Symposium on Computational Geometry, pages 251-257, 1987. Google Scholar
  8. K. Clarkson, S. Kapoor, and P. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log^2/3 n) time. Manuscript, 1988. Google Scholar
  9. G. Das and G. Narasimhan. Geometric searching and link distance. In Proc. of the 2nd Workshop of Algorithms and Data Structures, pages 261-272, 1991. Google Scholar
  10. M. de Berg. On rectilinear link distance. Computational Geometry: Theory and Applications, 1:13-34, 1991. Google Scholar
  11. J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4(2):63-97, 1994. Google Scholar
  12. H. Imai and T. Asano. Efficient algorithms for geometric graph search problems. SIAM Journal on Computing, 15(2):478-494, 1986. Google Scholar
  13. D. T. Lee, C. D. Yang, and T. H. Chen. Shortest rectilinear paths among weighted obstacles. International Journal of Computational Geometry and Applications, 1(2):109-124, 1991. Google Scholar
  14. J. S. B. Mitchell. An optimal algorithm for shortest rectilinear paths among obstacles. Abstracts of the 1st Canadian Conference on Computational Geometry, 1989. Google Scholar
  15. J. S. B. Mitchell. L₁ shortest paths among polygonal obstacles in the plane. Algorithmica, 8(1):55-88, 1992. Google Scholar
  16. J. S. B. Mitchell, V. Polishchuk, and M. Sysikaski. Minimum-link paths revisited. CGTA, 47:651-667, 2014. Google Scholar
  17. J. S. B. Mitchell, V. Polishchuk, M. Sysikaski, and H. Wang. An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. In Proc. of the 42nd International Colloquium on Automata, Languages and Programming, pages 947-959, 2015. Google Scholar
  18. J. S. B. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica, 8:431-459, 1992. Google Scholar
  19. V. Polishchuk and J. S. B. Mitchell. k-Link rectilinear shortest paths among rectilinear obstacles in the plane. In Proc. of the 17th Canadian Conference on Computational Geometry (CCCG), pages 101-104, 2005. Google Scholar
  20. M. Sato, J. Sakanaka, and T. Ohtsuki. A fast line-search method based on a tile plane. In Proc. of the IEEE International Symposium on Circuits and Systems, pages 588-597, 1987. Google Scholar
  21. S. Schuierer. An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon. International Journal of Computational Geometry and Applications, 6:205-226, 1996. Google Scholar
  22. H. Wang. Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane. arXiv:1703.04466, 2017. Google Scholar
  23. Y.-F. Wu, P. Widmayer, M. D. F. Schlag, and C. K. Wong. Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computers, 36:321-331, 1987. Google Scholar
  24. C. D. Yang, D. T. Lee, and C. K. Wong. On bends and lengths of rectilinear paths: A graph-theoretic approach. Int. J. Comput. Geom. Appl., 02:61-74, 1992. Google Scholar
  25. C. D. Yang, D. T. Lee, and C. K. Wong. Rectilinear path problems among rectilinear obstacles revisited. SIAM Journal on Computing, 24:457-472, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact