Tight Bounds for Illuminating and Covering of Orthotrees with Vertex Lights and Vertex Beacons
Tóm tắt
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.
Tài liệu tham khảo
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)