No Access

LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS

YOAV AMIT

Department of Computer Science, Stony Brook University, Stony Brook, New York 11794, USA

Search for more papers by this author

JOSEPH S. B. MITCHELL

Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, New York 11794, USA

Search for more papers by this author

, and

ELI PACKER

IBM Corporation, Haifa Research Lab, Israel

Search for more papers by this author

https://doi.org/10.1142/S0218195910003451Cited by:22 (Source: Crossref)

Abstract

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.

A preliminary version of this work appeared in the Workshop on Algorithm Engineering and Experiments, SIAM Proceedings in Applied Mathematics, pages 120–134, 2007.

Partially supported by grants from the National Science Foundation (ACI-0328930, CCF-0431030, CCF-0528209), Metron Aviation, and NASA Ames (NAG2-1620).

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

A. Aggarwal, The art gallery theorem: Its variations, applications and algorithmic aspects, PhD thesis, John Hopkins University, 1984 . Google Scholar
T. Auer and M. Held, Heuristics for the generation of random polygons, Proc. 8th Canadian Conf. Computational Geometry pp. 38–43. Google Scholar
D. Avis and G. Toussaint, Patt. Recogn. 13, 295 (1981), DOI: 10.1016/0031-3203(81)90002-9. Google Scholar
B. Ben-Mosheet al., Computing the visibility graph of points within a polygon, Proc. 20th ACM Symp. Computational Geometry pp. 27–35. Google Scholar
B. Ben-Moshe, M. J. Katz and J. S. B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, Proc. 16th ACM-SIAM Symposium on Discrete Algorithms pp. 515–524. Google Scholar
A. Bottino and A. Laurentini, A new art gallery algorithm for sensor location, Proc. 2nd Int. Conf. Informatics in Control, Automation and Robotics (INSTICC Press, 2005) pp. 242–249. Google Scholar
A. Bottino and A. Laurentini , Experimental results show near-optimality of a sensor location algorithm , Proc. IEEE Int. Conf. Robotics and Biomimetics . Google Scholar
H. Brönnimann and M. Goodrich, Discr. Comput. Geom. 14, 263 (1995). Google Scholar
O. Cheong, A. Efrat and S. Har-Peled, On finding a guard that sees most and a shop that sells most, Proc. 15th ACM-SIAM Symp. Discrete Algorithms pp. 1098–1107. Google Scholar
V. Chvatal, J. Comb. Th. Series B 18, 39 (1975), DOI: 10.1016/0095-8956(75)90061-1. Crossref, Web of Science, Google Scholar
A. Deshpandeet al., A pseudopolynomial time O(log2)-approximation algorithm for art gallery problems, Proc. 10th Workshop on Algorithms and Data Structures pp. 163–174. Google Scholar
A. Efrat and S. Har-Peled, Inform. Process. Lett. 100(6), 238 (2006), DOI: 10.1016/j.ipl.2006.05.014. Crossref, Web of Science, Google Scholar
S. Fisk, J. Comb. Th. Series B 24, 374 (1978), DOI: 10.1016/0095-8956(78)90059-X. Crossref, Web of Science, Google Scholar
S. K. Ghosh, Approximation algorithms for art gallery problems, Proc. Canadian Information Processing Society Congress pp. 429–434. Google Scholar
S. K. Ghosh and D. M. Mount, SIAM J. Comput. 20(5), 888 (1991), DOI: 10.1137/0220055. Crossref, Web of Science, Google Scholar
H. González-Banos and J.-C. Latombe, A randomized art-gallery algorithm for sensor placement, Proc. 17th ACM Symp. Computational Geometry pp. 232–240. Google Scholar
J. Hershberger, Algorithmica 4(1), 141 (1989), DOI: 10.1007/BF01553883. Crossref, Web of Science, Google Scholar
B. Joe and R. B. Simpson, BIT 27, 458 (1987), DOI: 10.1007/BF01937271. Crossref, Web of Science, Google Scholar
G. D. Kazakakis and A. A. Argyros, Fast positioning of limited visibility guards for inspection of 2D workspaces, Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems pp. 2843–2848. Google Scholar
J. M. Keil, SIAM J. Computing 14, 799 (1985), DOI: 10.1137/0214056. Crossref, Web of Science, Google Scholar
J. King, A 4-approximation algorithm for guarding 1.5-dimensional terrains, Proc.7th Latin American Symp. Theoretical Informatics3887, Lecture Notes Comput. Sci. (Springer-Verlag, 2006) pp. 629–640. Google Scholar
D. T. Lee and A. K. Lin, IEEE Trans. Inform. Th. 32(2), 276 (1986), DOI: 10.1109/TIT.1986.1057165. Crossref, Web of Science, Google Scholar
B. J. Nilsson, Approximate guarding of monotone and rectilinear polygons, Proc. 32nd Int. Colloq. Automata Lang. Prog.3580, Lecture Notes Computer Science (Springer-Verlag, 2005) pp. 1362–1373. Google Scholar
E. Packer, Computing multiple watchman routes, Proc. 7th Int. Workshop on Experimental Algorithms pp. 114–128. Google Scholar
J. O'Rourke , Art Gallery Theorems and Algorithms ( Oxford University Press , Oxford , 1987 ) . Google Scholar
T. Shermer, Proc. IEEE 80(9), 1384 (1992), DOI: 10.1109/5.163407. Crossref, Web of Science, Google Scholar
J. Urrutia, Handbook of Computational Geometry, eds. J. Sack and J. Urrutia (Elsevier Science Publishers, Amsterdam, 2000) pp. 973–1027. Crossref, Google Scholar
C. Worman and M. Keil, Int. J. Comput. Geom. Appl. 17(2), 105 (2007), DOI: 10.1142/S0218195907002264. Link, Web of Science, Google Scholar

Vol. 20, No. 05

Metrics

Downloaded 86 times

History

Received 27 May 2009

Revised 3 December 2009

Keywords

PDF download

LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS

Abstract

Recommended