Document Open Access Logo

Shortest Paths in the Plane with Obstacle Violations

Authors John Hershberger, Neeraj Kumar, Subhash Suri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.49.pdf
  • Filesize: 499 kB
  • 14 pages

Document Identifiers

Author Details

John Hershberger
Neeraj Kumar
Subhash Suri

Cite As Get BibTex

John Hershberger, Neeraj Kumar, and Subhash Suri. Shortest Paths in the Plane with Obstacle Violations. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.49

Abstract

We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for k <= h. Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of Theta(kn) on the size of this map, and show that it can be computed in O(k^2 n log n) time, where n is the total number of obstacle vertices.

Subject Classification

Keywords
  • Shortest paths
  • Polygonal obstacles
  • Continuous Dijkstra
  • Obstacle crossing
  • Visibility

Metrics

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

References

  1. M. Abellanas, A. García, F. Hurtado, J. Tejel, and J. Urrutia. Augmenting the connectivity of geometric graphs. Computational Geometry, 40(3):220-230, 2008. Google Scholar
  2. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice hall, 1993. Google Scholar
  3. T. Asano. An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE TRANSACTIONS (1976-1990), 68(9):557-559, 1985. Google Scholar
  4. T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons. Algorithmica, 1(1-4):49-63, 1986. Google Scholar
  5. J.-L. De Carufel, C. Grimm, A. Maheshwari, and M. Smid. Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. In 15th Scandinavian Symposium and Workshops on Algorithm Theory, pages 27:1-27:14, 2016. Google Scholar
  6. T. M. Chan. Low-dimensional linear programming with violations. SIAM Journal on Computing, 34(4):879-893, 2005. Google Scholar
  7. D. Z. Chen and H. Wang. Computing shortest paths among curved obstacles in the plane. ACM Trans. Algorithms, 11(4):26:1-26:46, 2015. Google Scholar
  8. H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317-340, 1986. Google Scholar
  9. S. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, and H. Yıldız. Geometric k shortest paths. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616-1625, 2015. Google Scholar
  10. M. Farshi, P. Giannopoulos, and J. Gudmundsson. Improving the stretch factor of a geometric network by edge augmentation. SIAM Journal on Computing, 38(1):226-240, 2008. Google Scholar
  11. S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing, 20(5):888-910, 1991. Google Scholar
  12. L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. Google Scholar
  13. S. Har-Peled and V. Koltun. Separability with outliers. 16th International Symposium on Algorithms and Computation, pages 28-39, 2005. Google Scholar
  14. J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry, 4(2):63-97, 1994. Google Scholar
  15. J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6):2215-2256, 1999. Google Scholar
  16. J. Hershberger, S. Suri, and H. Yıldız. A near-optimal algorithm for shortest paths among curved obstacles in the plane. In Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, pages 359-368, 2013. Google Scholar
  17. S. Kapoor and S. N. Maheshwari. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 172-182, 1988. Google Scholar
  18. D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, 1983. Google Scholar
  19. D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984. Google Scholar
  20. A. Maheshwari, S. C. Nandy, D. Pattanayak, S. Roy, and M. Smid. Geometric path problems with violations. Algorithmica, pages 1-24, 2016. Google Scholar
  21. J. Matoušek. On geometric optimization with few violated constraints. Discrete &Computational Geometry, 14(4):365-384, 1995. Google Scholar
  22. J. S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3(1):83-105, 1991. Google Scholar
  23. J. S. B. Mitchell. Shortest paths among obstacles in the plane. International Journal of Computational Geometry &Applications, 6(3):309-332, 1996. Google Scholar
  24. J. S. B. Mitchell and C. H. Papadimitriou. The weighted region problem: finding shortest paths through a weighted planar subdivision. Journal of the ACM (JACM), 38(1):18-73, 1991. Google Scholar
  25. M. H. Overmars and E. Welzl. New methods for computing visibility graphs. In Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 164-171, 1988. Google Scholar
  26. H. Rohnert. Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters, 23(2):71-76, 1986. Google Scholar
  27. T. Roos and P. Widmayer. k-violation linear programming. Information Processing Letters, 52(2):109-114, 1994. Google Scholar
  28. J. A. Storer and J. H. Reif. Shortest paths in the plane with polygonal obstacles. Journal of the ACM (JACM), 41(5):982-1012, 1994. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact