Abstract
We consider two variants of the Art Gallery Problem: illuminating orthotrees with a minimum set of vertex lights, and covering orthotrees with a minimum set of vertex beacons. An orthotree P is a simply connected orthogonal polyhedron that is the union of a set S of cuboids glued face to face such that the graph whose vertices are the cuboids of S, two of which are adjacent if they share a common face, is a tree. A point p illuminates a point \(q \in P\) if the line segment \(\ell\) joining them is contained in P. A beacon b is a point in P that pulls other points in P towards itself similarly to the way a magnet attracts ferrous particles. We say that a beacon bcoversp if when b starts pulling p, p does not get stuck at a point of P before it reaches b. This happens, for instance if p reaches a point \(p'\) such that there is an \(\epsilon >0\) such that any point in P at distance at most \(\epsilon\) from \(p'\) is farther away from \(p'\) than q (there is another pathological case that we will not detail in this abstract). In this paper we prove that any orthotree P with n vertices can be illuminated using at most \(\lfloor n/8 \rfloor\) light sources placed at vertices of P, and that all of the points in P can always be covered with at most \(\lfloor n/12 \rfloor\) vertex beacons. Both bounds are tight.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aldana-Galván, I., Álvarez-Rebollar, J.L., Catana-Salazar, J.C., Jiménez-Salinas, M., Solís-Villarreal, E., Urrutia, J.: Minimizing the solid angle sum of orthogonal polyhedra and guarding them with \(\frac{\pi }{2}\)-edge guards. In: Proceedings of the 28th Canadian Conference on Computational Geometry, Vancouver, August 3-5, pp. 175–181 (2016)
Aldana-Galván, I., Álvarez-Rebollar, J.L., Catana-Salazar, J.C., Marín-Nevárez, N., Solís-Villarreal, E., Urrutia, J., Velarde, C.: Covering orthotrees with guards and beacons. In: In proceedings of XVII Spanish Meeting on Computational Geometry, Alicante, Spain, July 26–28, pp. 56–68 (2017)
Bae, S.W., Shin, C.S., Vigneron, A.E.: Tight bounds for beacon-based coverage in simple rectilinear polygons. To appear in Computational Geometry (2019). https://doi.org/10.1016/j.comgeo.2019.02.002
Benbernou, N.M., Demaine, E.D., Demaine, M.L., Kurdia, A., O’Rourke, J., Toussaint, G., Urrutia, J., Viglietta, G.: Edge-guarding orthogonal polyhedra. In: Proceedings of the 23rd Canadian Conference on Computational Geometry, Toronto, August 10–12, pp. 461–466 (2011)
Biro, M.: Beacon-based routing and guarding. Ph.D. thesis, State University of New York at Stony Brook (2013)
Biro, M., Gao, J., Iwerks, J.B., Kostitsyna, I., Mitchell, J.S.: Beacon-based routing and coverage. In: 21st Fall Workshop on Computational Geometry, New York, November 4–5 (2011)
Chvátal, V.: A combinatorial theorem in plane geometry. J. Comb Theory Ser B 18(1), 39–41 (1975)
Cleve, J.: Combinatorics of beacon-based routing and guarding in three dimensions. Master’s thesis, Freie Universität Berlin (2017)
Cleve, J., Mulzer, W.: Combinatorics of beacon-based routing in three dimensions. In: Latin American Symposium on Theoretical Informatics, Buenos Aires, April 16-19, pp. 346–360. Springer (2018)
Damian, M., Flatland, R.: Unfolding low-degree orthotrees with constant refinement. In: 30th Canadian Conference on Computational Geometry, Winnipeg, August 8–10. Elsevier (2018)
Damian, M., Flatland, R.: Unfolding orthotrees with constant refinement. arXiv preprint arXiv:1811.01842 (2018)
Iwerks, J.G.: Combinatorics and complexity in geometric visibility problems. Ph.D. thesis, State University of New York at Stony Brook (2012)
O’Rourke, J.: Art Gallery Theorems and Algorithms, vol. 57. Oxford University Press Inc., New York (1987)
Shermer, T.C.: Recent results in art galleries. Proc. IEEE 80, 1384–1384 (1992)
Shermer, T.C.: A combinatorial bound for beacon-based routing in orthogonal polygons. (2015) arXiv:1507.03509
Shermer, T.C.: A combinatorial bound for beacon-based routing in orthogonal polygons. In: Proceedings of the 27th Canadian Conference on Computational Geometry, Kingston, Ontario, August 10–12, pp. 213–219 (2015)
Tomás, A.P.: Guarding thin orthogonal polygons is hard. In: International Symposium on Fundamentals of Computation Theory, pp. 305–316. Springer (2013)
Urrutia, J.: Art gallery and illumination problems. In: Handbook of computational geometry, pp. 973–1027. Elsevier (2000)
Viglietta, G.: Guarding and searching polyhedra. Ph.D. thesis, University of Pisa (2012)
Viglietta, G.: Face-guarding polyhedra. Comput. Geom. 47(8), 833–846 (2014)
Acknowledgements
We thank the anonymous referee for his careful reading and comments of paper. His suggestions helped us to improve the readability of our paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
J. Urrutia was partially supported by PAPIIT Grant IN102117 from Universidad Nacional Autónoma de México.
I. Aldana-Galván, J.L. Álvarez-Rebollar, J.C. Catana-Salazar, N. Marín, and E. Solís-Villarreal were partially supported by PAEP from Universidad Nacional Autónoma de México.
Rights and permissions
About this article
Cite this article
Aldana-Galván, I., Álvarez-Rebollar, J.L., Catana-Salazar, J.C. et al. Tight Bounds for Illuminating and Covering of Orthotrees with Vertex Lights and Vertex Beacons. Graphs and Combinatorics 36, 617–630 (2020). https://doi.org/10.1007/s00373-020-02141-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02141-4