Sweeping simple polygons with a chain of guards

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Sweeping simple polygons with a chain of guards

Full text

Pdf (969 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 927 - 936

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Alon Efrat	Computer Science Dept., Stanford University, 353 Serra Mall, Stanford, CA
Leonidas J. Guibas	Computer Science Dept., Stanford University, 353 Serra Mall, Stanford, CA
Sariel Har-Peled	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
David C. Lin	Computer Science, Dept., Stanford University, 353 Serra Mall, Stanford, CA
Joseph S. B. Mitchell	Dept. Applied Math, University at Stony Brook, Stony Brook, NY
T. M. Murali	Compaq Computer Corporation, Cambridge Research Lab, One Kendall Square, Bldg. 700, Cambridge, MA and Stanford University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 37, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. Agarwal and M. Sharir. Arrangements. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishers B.V. North-Holland, Amsterdam. To appear.
	2	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	3	A. Aggarwal , H. Booth , J. O'Rourke , S. Suri, Finding minimal convex nested polygons, Information and Computation, v.83 n.1, p.98-110, Oct. 1989 [doi>10.1016/0890-5401(89)90049-7]
	4	E. M. Arkin, j. S. B. Mitchell, and C. Piatko. Minimum-link watchman tours. Report, University at Stony Brook, 1994.
	5	E. M. Arkin, J. S. B. Mitchell, and S. Suri. Logarithmic-time link path queries in a simple polygon. Internat. J. Comput. Geom. Appl., 5(4):369- 395, 1995.
	6	Svante Carlsson , Håkan Jonsson, Computing a Shortest Watchman Path in a Simple Polygon in Polynomial-Time, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.122-134, August 16-18, 1995
	7	B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and j. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12:54-68, 1994.
	8	Wei-Pand Chin , Simeon Ntafos, Shortest watchman routes in simple polygons, Discrete & Computational Geometry, v.6 n.1, p.9-31, 1991 [doi>10.1007/BF02574671]
	9	D. Crass, I. Suzuki, and M. Yamashita. Searching for a mobile intruder in a corridor- the open edge variant of the polygon search problem. Internat. J. Comput. Geom. Appl., 5:397-412, 1995.
	10	M. de Berg. E~cient algorithms .for ray shooting and hidden surface removal. Ph.D. dissertation, Dept. Comput. Sci., Utrecht Univ., Utrecht, Netherlands, 1992.
	11	Hristo N. Djidjev , Andrzej Lingas , Jörg-Rüdiger Sack, An O(n log n) algorithm for computing the link center of a simple polygon, Discrete & Computational Geometry, v.8 n.2, p.131-152, 1992 [doi>10.1007/BF02293040]
	12	Leonidas J. Guibas , Jean-Claude Latombe , Steven M. LaValle , David Lin , Rajeev Motwani, Visibility-Based Pursuit-Evasion in a Polygonal Environment, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.17-30, August 06-08, 1997
	13	Dan Halperin, Arrangements, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	14	Dan Halperin , Micha Sharir, Arrangements and their applications in robotics: recent developments, Proceedings of the workshop on Algorithmic foundations of robotics, p.495-511, May 1995, San Francisco, California, United States
	15	P. J. Heffernan. An optimal algorithm for the twoguard problem. Internat. J. Comput. Geom. Appl., 6:15-44, 1996.
	16	Frank Hoffmann , Michael Kaufmann , Klaus Kriegel, The Art Gallery theorem for polygons with holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.39-48, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185346]
	17	C. Icking and R. Klein. The two guards problem. Internat. j. Comput. Geom. Appl., 2(3):257-285, 1992.
	18	Y. Ke, An efficient algorithm for link-distance problems, Proceedings of the fifth annual symposium on Computational geometry, p.69-78, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73841]
	19	Yan Ke, Polygon visibility algorithms for weak visibility and link distance problems, Johns Hopkins University, Baltimore, MD, 1990
	20	Rolf Klein, Moving Along a Street, Proceedings of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, p.123-140, March 21-22, 1991
	21	S. M. LaValle, D. Lin, L. j. Guibas, J.-C. Latombe, and R. Motwani. Finding an unpredictable target in a workspace with obstacles. In Proc. IEEE Internat. Conf. Robot. Aurora., Apr. 1997. To appear.
	22	N. Megiddo , S. L. Hakimi , M. R. Garey , D. S. Johnson , C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM (JACM), v.35 n.1, p.18-44, Jan. 1988 [doi>10.1145/42267.42268]
	23	Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
	24	T. D. Parsons. Pursuit-evasion in a graph. In Y. Alavi and D. Lick, editors, Theory and Applications of Graphs, volume 642 of Lecture Notes Math., pages 426-441. Springer-Verla.g, Berlin, West Germany, 1976.
	25	Marco Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	26	Subhash Suri, Minimum link paths in polygons and related problems, 1987
	27	S. Suri. On some link distance problems in a simple polygon. IEEE Trans. Robot. Aurora., 6:108-113, 1990.
	28	Ichiro Suzuki , Masafumi Yamashita, Searching for a mobile intruder in a polygonal region, SIAM Journal on Computing, v.21 n.5, p.863-888, Oct. 1992 [doi>10.1137/0221051]
	29	X. Tan. Searching a simple polygon by a k-searcher. Unpublished manuscript, 1999.
	30	L. H. Tseng, P. Heffernan, and D. T. Lee. Twoguard walkability of simple polygons. Internat. J. Compu~. Geom. Appl., 8(1):85-116, 1998.
	31	J. Urrutia. Art gallery and illumination problems. in J.-R. Sack and .}. Urrutia, editors, Handbook on Computational Geometry, Elsevier Science Publishers B.V. North-Holland, Amsterdam. To appear.

CITED BY 9

	Alon Efrat , Sariel Har-Peled , Leonidas J. Guibas , T. M. Murali, Morphing between polylines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 07-09, 2001, Washington, D.C., United States
	Steven M. LaValle , Borislav H. Simov , Giora Slutzki, An algorithm for searching a polygonal region with a flashlight, Proceedings of the sixteenth annual symposium on Computational geometry, p.260-269, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Uǧur Murat Erdem , Stan Sclaroff, Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements, Computer Vision and Image Understanding, v.103 n.3, p.156-169, September 2006
	Xuehou Tan, Sweeping simple polygons with the minimum number of chain guards, Information Processing Letters, v.102 n.2-3, p.66-71, April, 2007
	Aman Kansal , William Kaiser , Gregory Pottie , Mani Srivastava , Gaurav Sukhatme, Reconfiguration methods for mobile sensor networks, ACM Transactions on Sensor Networks (TOSN), v.3 n.4, p.22-es, October 2007
	Micah Adler , Harald Räcke , Naveen Sivadasan , Christian Sohler , Berthold Vöcking, Randomized Pursuit-Evasion in Graphs, Combinatorics, Probability and Computing, v.12 n.3, p.225-244, May 2003
	Xuehou Tan, A unified and efficient solution to the room search problem, Computational Geometry: Theory and Applications, v.40 n.1, p.45-60, May, 2008
	Xuehou Tan, An efficient algorithm for the three-guard problem, Discrete Applied Mathematics, v.156 n.17, p.3312-3324, October, 2008
	Peter Brass , Kyue D. Kim , Hyeon-Suk Na , Chan-Su Shin, Escaping offline searchers and isoperimetric theorems, Computational Geometry: Theory and Applications, v.42 n.2, p.119-126, February, 2009