Full bibliography
A coloring algorithm for finding connected guards in art galleries
Resource type
Author/contributor
- Pinciu, Val (Author)
Title
A coloring algorithm for finding connected guards in art galleries
Abstract
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.
Proceedings Title
Discrete Mathematics & Theoretical Computer Science
Publisher
Springer Verlag
Date
2003
Volume
2731
Pages
257-264
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN
03029743 (ISSN); 3540405054 (ISBN); 9783540405054 (ISBN)
Citation Key
pop00126
Language
English
Extra
4 citations (Crossref) [2023-10-31]
Citation Key Alias: lens.org/033-385-827-635-520
tex.type: [object Object]
Citation
Pinciu, V. (2003). A coloring algorithm for finding connected guards in art galleries. Discrete Mathematics & Theoretical Computer Science, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2731, 257–264. https://doi.org/10.1007/3-540-45066-1_20
Link to this record