LIPIcs.SWAT.2018.6.pdf
- Filesize: 0.7 MB
- 13 pages
Document
On Romeo and Juliet Problems: Minimizing Distance-to-Sight
Authors
Darren Strash 
-
Part of:
Volume:
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn, and Darren Strash. On Romeo and Juliet Problems: Minimizing Distance-to-Sight. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.6
Abstract
We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance these persons travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log^2 n) time for any two query positions where the two persons lie.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Mathematics of computing → Paths and connectivity problems
Keywords
- Visibility polygon
- shortest-path
- watchman problems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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. URL: http://dx.doi.org/10.20382/jocg.v7i2a5.
- 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. URL: http://dx.doi.org/10.1007/s00454-001-0089-9.
- 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. URL: http://dx.doi.org/10.1007/PL00009467.
- Wei-pang Chin and Simeon C. Ntafos. Optimum watchman routes. In Alok Aggarwal, editor, Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, Yorktown Heights, NY, USA, June 2-4, 1986, pages 24-33. ACM, 1986. URL: http://dx.doi.org/10.1145/10515.10518.
- Wei-pang Chin and Simeon C. Ntafos. Optimum watchman routes. Inf. Process. Lett., 28(1):39-44, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90141-X.
- Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell. Touring a sequence of polygons. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 473-482. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780612.
- Adrian Dumitrescu and Csaba D. Tóth. Watchman tours for polygons with holes. Comput. Geom., 45(7):326-333, 2012. URL: http://dx.doi.org/10.1016/j.comgeo.2012.02.001.
- Anurag Ganguli, Jorge Cortes, and Francesco Bullo. Visibility-based multi-agent deployment in orthogonal environments. In Proceedings of the 2007 American Control Conference (ACC '07), pages 3426-3431, 2007. URL: http://dx.doi.org/10.1109/ACC.2007.4283034.
- Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90041-X.
- Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Endre Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987. URL: http://dx.doi.org/10.1007/BF01840360.
- John Hershberger. A new data structure for shortest path queries in a simple polygon. Inf. Process. Lett., 38(5):231-235, 1991. URL: http://dx.doi.org/10.1016/0020-0190(91)90064-O.
- John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms, 18(3):403-431, 1995. URL: http://dx.doi.org/10.1006/jagm.1995.1017.
-
Ramtin Khosravi and Mohammad Ghodsi. The fastest way to view a query point in simple polygons. In Proceedings of the 21st European Workshop on Computational Geometry, pages 187-190, 2005.
- Joseph S. B. Mitchell. Approximating watchman routes. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 844-855. SIAM, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.60.
- Haitao Wang. Quickest visibility queries in polygonal domains. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, volume 77 of LIPIcs, pages 61:1-61:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2017.61.
-
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, pages 216-221, 1993.