TY - GEN
T1 - Locating guards for visibility coverage of polygons
AU - Amit, Yoav
AU - Mitchell, Joseph S.B.
AU - Packer, Eli
PY - 2007
Y1 - 2007
N2 - We propose heuristics for visibility coverage of a polygon with the fewest point guards. This optimal coverage problem, often called the "art gallery problem", is known to be NP-hard, so most recent research has focused on heuristics and approximation methods. We evaluate our heuristics through experimentation, comparing the upper bounds on the optimal guard number given by our methods with computed lower bounds based on heuristics for placing a large number of visibility-independent "witness points". We give experimental evidence that our heuristics perform well in practice, on a large suite of input data; often the heuristics give a provably optimal result, while in other cases there is only a small gap between the computed upper and lower bounds on the optimal guard number.
AB - We propose heuristics for visibility coverage of a polygon with the fewest point guards. This optimal coverage problem, often called the "art gallery problem", is known to be NP-hard, so most recent research has focused on heuristics and approximation methods. We evaluate our heuristics through experimentation, comparing the upper bounds on the optimal guard number given by our methods with computed lower bounds based on heuristics for placing a large number of visibility-independent "witness points". We give experimental evidence that our heuristics perform well in practice, on a large suite of input data; often the heuristics give a provably optimal result, while in other cases there is only a small gap between the computed upper and lower bounds on the optimal guard number.
UR - https://www.scopus.com/pages/publications/34547940824
U2 - 10.1137/1.9781611972870.12
DO - 10.1137/1.9781611972870.12
M3 - Conference contribution
SN - 0898716284
SN - 9780898716283
T3 - Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
SP - 120
EP - 134
BT - Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
PB - Society for Industrial and Applied Mathematics Publications
T2 - 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Y2 - 6 January 2007 through 6 January 2007
ER -