We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Tight Bounds for Illuminating and Covering of Orthotrees with Vertex Lights and Vertex Beacons.
- Authors
Aldana-Galván, I.; Álvarez-Rebollar, J. L.; Catana-Salazar, J. C.; Marín, N.; Solís-Villarreal, E.; Urrutia, J.; Velarde, C.
- 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 ∈ P if the line segment ℓ 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 ϵ > 0 such that any point in P at distance at most ϵ 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 ⌊ n / 8 ⌋ light sources placed at vertices of P, and that all of the points in P can always be covered with at most ⌊ n / 12 ⌋ vertex beacons. Both bounds are tight.
- Subjects
BEACONS; LIGHT sources; COMMERCIAL art galleries; POLYHEDRA
- Publication
Graphs & Combinatorics, 2020, Vol 36, Issue 3, p617
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-020-02141-4