Orthogonal art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Suppose that all walls (interior as well as exterior) are horizontal or vertical and each interior wall has an arbitrarily placed, arbitrarily small doorway. We show t...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2006-07, Vol.154 (11), p.1563-1569
Main Authors: Hutchinson, Joan, Kündgen, André
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Art gallery theorem
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
Geometry
Interior walls
Mathematics
Orthogonal
Pattern recognition. Digital image processing. Computational geometry
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Suppose that all walls (interior as well as exterior) are horizontal or vertical and each interior wall has an arbitrarily placed, arbitrarily small doorway. We show that the minimum number of guards that suffice to guard all such art galleries with n vertices and m interior walls is min { ⌊ ( n + 2 m ) / 4 ⌋ , ⌊ ( n + 3 ⌊ n / 2 ⌋ + m - 2 ) / 8 ⌋ } .
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2006.01.006