Document Open Access Logo

Minimizing Distance-to-Sight in Polygonal Domains

Author Eunjin Oh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.59.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Eunjin Oh
  • Max Planck Institute for Informatics Saarbrücken, Germany

Cite AsGet BibTex

Eunjin Oh. Minimizing Distance-to-Sight in Polygonal Domains. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.59

Abstract

In this paper, we consider the quickest pair-visibility problem in polygonal domains. Given two points in a polygonal domain with h holes of total complexity n, we want to minimize the maximum distance that the two points travel in order to see each other in the polygonal domain. We present an O(n log^2 n+h^2 log^4 h)-time algorithm for this problem. We show that this running time is almost optimal unless the 3sum problem can be solved in O(n^{2-epsilon}) time for some epsilon>0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Visibility in polygonal domains
  • shortest path in polygonal domains

Metrics

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

References

  1. Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn, and Darren Strash. On Romeo and Juliet Problems: Minimizing Distance-to-Sight. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 2018. Google Scholar
  2. 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. Journal of Computational Geometry, 7(2):77-100, 2016. Google Scholar
  3. Danny Z. Chen and Haitao Wang. Computing Shortest Paths Among Curved Obstacles in the Plane. ACM Transactions on Algorithms, 11(4):26:1-26:46, 2015. Google Scholar
  4. Danny Z. Chen and Haitao Wang. Computing the Visibility Polygon of an Island in a Polygonal Domain. Algorithmica, 77(1):40-64, 2017. Google Scholar
  5. Richard Cole. Parallel Merge Sort. SIAM Journal on Computing, 17(4):770-785, 1988. Google Scholar
  6. David P. Dobkin and Diane L. Souvaine. Computational geometry in a curved world. Algorithmica, 5(1):421-457, 1990. Google Scholar
  7. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Compututational Geometry: Theory and Applications, 45(4):140-152, 2012. Google Scholar
  8. Anurag Ganguli, Jorge Cortes, and Francesco Bullo. Visibility-based multi-agent deployment in orthogonal environments. In Proceedings of American Control Conference, pages 3426-3431, 2007. Google Scholar
  9. Michael T. Goodrich, Steven B. Shauck, and Sumanta Guha. Parallel methods for visibility and shortest-path problems in simple polygons. Algorithmica, 8(1):461-486, 1992. Google Scholar
  10. John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6):2215-2256, 1999. Google Scholar
  11. S. Kapoor, S. N. Maheshwari, and J. S. B. Mitchell. An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane. Discrete & Computational Geometry, 18(4):377-383, 1997. Google Scholar
  12. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  13. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166-204, 1981. Google Scholar
  14. Haitao Wang. Quickest Visibility Queries in Polygonal Domains. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77, pages 61:1-61:16, 2017. Google Scholar
  15. Erik L. Wynters and Joseph S. B. Mitchell. Shortest Paths for a Two-Robot Rendez-Vous. In Proceedings of the 5th Canadian Conference on Computational Geometry (CCCG 1993), pages 216-221, 1993. 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 Imprint Privacy Contact