Art gallery theorems for guarded guards - Michael, T.S.; Pinciu, V. (Computational Geometry: Theory and Applications, 2003)
We prove two art gallery theorems in which the guards must guard one another in addition to the gallery. A set G of points (the guards) in a simple closed polygon (the art gallery) is a guarded guard set provided (i) every point in the polygon is visible to some point in G; and (ii) every point in G is visible to some other point in G. We prove that a polygon with n sides always has a guarded guard set of cardinality ⌊(3n-1)/7⌋ and that this bound is sharp (n5); our result corrects an erroneous formula in the literature. We also use a coloring argument to give an entirely new proof that the corresponding sharp function for orthogonal polygons is ⌊n/3⌋ for n≤6; this result was originally established by induction by Hernández-Peñalver. © 2003 Elsevier B.V.
16 citations (Crossref) [2023-10-31]
Keywords: Art gallery theorems; Visibility in polygons; dept.mat

A coloring algorithm for finding connected guards in art galleries - Pinciu, Val (Discrete Mathematics & Theoretical Computer Science, 2003)
In this paper we consider a variation of the Art Gallery Problem. A set of points script G sign in a polygon Pn is a connected guard set for Pn provided that is a guard set and the visibility graph of the set of guards script G sign in Pn is connected. We use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any polygon with n sides is ⌊(n - 2)/2⌋. This result was originally established by induction by Hernández-Peńalver [3]. From this result it easily follows that if the art gallery is orthogonal (each interior angle is 90° or 270°), then the minimum number of connected guards is n/2 - 2. © Springer-Verlag Berlin Heidelberg 2003.
4 citations (Crossref) [2023-10-31] Citation Key Alias: lens.org/033-385-827-635-520 tex.type: [object Object]
Keywords: Algorithms; Art gallery; Artificial intelligence; Coloring algorithms; Computer science; Computers; Visibility graphs; dept.mat

Connected guards in orthogonal art galleries - Pinciu, Val (International Conference on Computational Science and Its Applications, 2003)
In this paper we consider a variation of the Art Gallery Problem for orthogonal polygons. A set of points in a polygon Pn is a connected guard set for Pn provided that is a guard set and the visibility graph of the set of guards in Pn is connected. The polygon P n is orthogonal provided each interior angle is 90° or 270°. First we use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any orthogonal polygon with n sides is n/2-2. This result was originally established by induction by Hernández-Peñalver. Then we prove a new result for art galleries with holes: we show that n/2-h connected guards are always sufficient to watch an orthogonal art gallery with n walls and h holes. This result is sharp when n = 4h + 4. We also construct galleries that require at least n/2-h-1 connected guards, for all n and h. © Springer-Verlag 2003.
4 citations (Crossref) [2023-10-31] tex.type: Proceedings paper
Keywords: Art gallery; Art gallery problem; Geometry; New results; Visibility graphs; Watches; dept.mat

Computer-generated fractals using iterated function systems - Stiegler, Cynthia Joy Gayda (2003)
Citation Key Alias: lens.org/061-542-555-937-702
Keywords: dept.mat