Document Open Access Logo

Shortest Path to a Segment and Quickest Visibility Queries

Authors Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, Topi Talvitie

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.658.pdf
  • Filesize: 0.65 MB
  • 16 pages

Document Identifiers

Author Details

Esther M. Arkin
Alon Efrat
Christian Knauer
Joseph S. B. Mitchell
Valentin Polishchuk
Günter Rote
Lena Schlipf
Topi Talvitie

Cite As Get BibTex

Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest Path to a Segment and Quickest Visibility Queries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 658-673, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.658

Abstract

We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.

Subject Classification

Keywords
  • path planning
  • visibility
  • query structures and complexity
  • persistent data structures
  • continuous Dijkstra

Metrics

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

References

  1. Esther M. Arkin, Joseph S. B. Mitchell, and Subhash Suri. Optimal link path queries in a simple polygon. In Proc. 3rd Ann. ACM-SIAM Symp. Discrete Algorithms (SODA'92), pages 269-279, 1992. Google Scholar
  2. Boris Aronov, Leonidas J. Guibas, Marek Teichmann, and Li Zhang. Visibility queries and maintenance in simple polygons. Discrete & Computational Geometry, 27(4):461-483, 2002. Google Scholar
  3. Prosenjit Bose, Anna Lubiw, and J. Ian Munro. Efficient visibility queries in simple polygons. Comput. Geom. Theory Appl., 23(3):313-335, November 2002. Google Scholar
  4. Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang, and Alexander Kröller. Efficient computation of visibility polygons. In 30th Europ. Workshop on Comput. Geom. (EuroCG'14), 2014. Google Scholar
  5. Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson. Finding the shortest watchman route in a simple polygon. Discrete & Computational Geometry, 22(3):377-402, 1999. Google Scholar
  6. CGAL. Computational Geometry Algorithms Library. URL: http://www.cgal.org.
  7. Bernard Chazelle. A theorem on polygon cutting with applications. In Proc. 23rd Annu. Sympos. Found. Comput. Sci. (FOCS'82), pages 339-349. IEEE, 1982. Google Scholar
  8. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. Ray shooting in polygons using geodesic triangulations. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez Artalejo, editors, Automata, Languages and Programming (ICALP), volume 510 of Lecture Notes in Computer Science, pages 661-673. Springer, 1994. Google Scholar
  9. Danny Z. Chen and Haitao Wang. Visibility and ray shooting queries in polygonal domains. In Proc. 13th Int. Conf. Algorithms Data Struct. (WADS'13), LNCS, pages 244-255, 2013. Google Scholar
  10. Yi-Jen Chiang and Roberto Tamassia. Optimal shortest path and minimum-link path queries between two convex polygons inside a simple polygonal obstacle. Int. J. Comput. Geometry Appl., 7(1/2):85-121, 1997. Google Scholar
  11. Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell. Touring a sequence of polygons. In Proc. 35th Symposium on Theory of Computing (STOC'03), pages 473-482, 2003. Google Scholar
  12. Adrian Dumitrescu and Csaba D. Tóth. Watchman tours for polygons with holes. Comput. Geom. Theory Appl., 45(7):326-333, 2012. Google Scholar
  13. 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 Sanjeev Khanna, editor, Proc. 26th Ann. ACM-SIAM Symp. Discrete Algorithms, (SODA'15), pages 1616-1625. SIAM, 2015. Google Scholar
  14. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry: Theory and Applications, 5:165-185, 1995. Google Scholar
  15. Subir Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, 2007. Google Scholar
  16. Subir Kumar Ghosh and David M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput., 20(5):888-910, 1991. Google Scholar
  17. J.E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. Taylor & Francis, 2nd edition, 2010. Google Scholar
  18. Allan Gr\danskOnlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Proc. 55th Ann. Sympos. Found. Comput. Sci. (FOCS'14), pages 621-630. IEEE, 2014. Google Scholar
  19. Leonidas J. Guibas, J. Hershberger, D. Leven, Micha Sharir, and R. E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987. Google Scholar
  20. Leonidas J. Guibas, Rajeev Motwani, and Prabhakar Raghavan. The robot localization problem. SIAM J. Comput., 26(4):1120-1138, August 1997. Google Scholar
  21. Olaf Andrew Hall-Holt. Kinetic Visibility. PhD thesis, Stanford University, 2002. Google Scholar
  22. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. Google Scholar
  23. P. J. Heffernan and Joseph S. B. Mitchell. An optimal algorithm for computing visibility in the plane. SIAM J. Comput., 24(1):184-201, 1995. Google Scholar
  24. John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18(3):403-431, 1995. Google Scholar
  25. John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput., 28(6):2215-2256, 1999. Google Scholar
  26. Rajasekhar Inkulu and Sanjiv Kapoor. Visibility queries in a polygonal region. Comput. Geom. Theory Appl., 42(9):852-864, 2009. Google Scholar
  27. B. Joe and R. B. Simpson. Correction to Lee’s visibility polygon algorithm. BIT, 27:458-473, 1987. Google Scholar
  28. Ramtin Khosravi and Mohammad Ghodsi. The fastest way to view a query point in simple polygons. In 21st European Workshop on Computational Geometry (EuroCG'05), pages 187-190. Eindhoven, 2005. Google Scholar
  29. Christian Knauer, Günter Rote, and Lena Schlipf. Shortest inspection-path queries in simple polygons. In 24th European Workshop on Computational Geometry (EuroCG'08), pages 153-156, 2008. Google Scholar
  30. D. T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14:393-410, 1984. Google Scholar
  31. Lin Lu, Chenglei Yang, and Jiaye Wang. Point visibility computing in polygons with holes. Journal of Information & Computational Science, 8(16):4165-4173, 2011. Google Scholar
  32. Joseph S. B. Mitchell. Shortest paths among obstacles in the plane. Internat. J. Comput. Geom. Appl., 6:309-332, 1996. Google Scholar
  33. Joseph S. B. Mitchell. Geometric shortest paths and network optimization. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 633-701. Elsevier, 2000. Google Scholar
  34. Joseph S. B. Mitchell. Shortest paths and networks. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 445-466. Elsevier, 2004. Google Scholar
  35. Joseph S. B. Mitchell. Approximating watchman routes. In Sanjeev Khanna, editor, Proc. 24th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA'13, pages 844-855. SIAM, 2013. Google Scholar
  36. Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. Comput. Geom. Theory Appl., 47(6):651-667, 2014. Google Scholar
  37. Joseph S. B. Mitchell, Günter Rote, and Gerhard J. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica, 8(1):431-459, 1992. Google Scholar
  38. Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Google Scholar
  39. Eli Packer. Computing multiple watchman routes. In Catherine C. McGeoch, editor, Experimental Algorithms, 7th International Workshop, WEA, Provincetown, MA, USA, volume 5038 of Lecture Notes in Computer Science, pages 114-128. Springer, 2008. Google Scholar
  40. S Suri and J O'Rourke. Worst-case optimal algorithms for constructing visibility polygons with holes. In Proc. 2nd Ann. Symp. Computational Geometry, pages 14-23. ACM, 1986. Google Scholar
  41. Subhash Suri. A linear time algorithm with minimum link paths inside a simple polygon. Computer Vision, Graphics and Image Processing, 35(1):99-110, 1986. Google Scholar
  42. Alireza Zarei and Mohammad Ghodsi. Query point visibility computation in polygons with holes. Comput. Geom. Theory Appl., 39(2):78-90, 2008. 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