Worst-case optimal algorithms for constructing visibility polygons with holes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Worst-case optimal algorithms for constructing visibility polygons with holes

Full text

Pdf (610 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the second annual symposium on Computational geometry table of contents

Yorktown Heights, New York, United States

Pages: 14 - 23

Year of Publication: 1986

ISBN:0-89791-194-6

Authors

S Suri	Department of Electrical Engineering & Computer Science The Johns Hopkins University, Baltimore, MD
J O'Rourke	Department of Electrical Engineering & Computer Science The Johns Hopkins University, Baltimore, MD

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/10515.10517 What is a DOI?

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.

	AA	T. Asano, T. Asano, L. Guibas, J. Hershberger tk H. Imai. "Visibility Polygon Search and Euclidean Shortest Paths,' Pro~. fgth F0~$, 1985, pp. 155-1~.
	Ch	Bernard Chaselle, Intersecting is easier than sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.125-134, December 1984 [doi>10.1145/800057.808674]
	CG	Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
	EA	H. El Gindy and D. Avis. "A Linear Algorithm for Computing the Visibility Polygon from a Point,' Journal of Algorithms, ~, pp. 186-197 (1981).
	El	H. El Gindy. "An Efficient Algorithm for Computing the Weak Visibility Polygon from an Edge in Simple Polygons,' Technical Report, School of Computer Science, McGill University, (Jan. 1984).
	Gr	E. Grc~swald. Topics From The Theory Of Numbers, Macmillan, New York, 1966.
	GH	L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
	IA	H. Imai, T. Asano & T. Asano. "Visibility of Disjoint Polygons,' Technical Report, Dept. of Math. Engineering and Instrumentation Physics, Faculty of Enginnering, University of Tokyo, Tokyo, Japan 113 (1985).
	LL	D. T. Lee and A. Lin. "Computing Visibility Polygon from an Edge,' Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University, (Jan. 1984).
	M	M. McKenna. "Worst-Case Optimal Hidden Surface Removal', Technical Report, The Johns Hopkins University, (March, 1986).
	SO	S. Suri and J. O'Rourke. "Worst-Case Optimal Algorithms For Constructing Visibility Polygons With Holes,' Technical Report, The Johns Hopkins University, (August 1985).
	We	Emo Welzl. "Constructing The Visibility Graph For n Line Segments In O (ne) Time,' Information Processin~ Letters, Volume 20, Number 4, 10 May, 1985.

CITED BY 9

	Evangelos Kranakis , M. Pocchiola, Enumeration and visibility problems in integer lattices (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.261-270, June 07-09, 1990, Berkley, California, United States
	Joseph S. B. Mitchell , Günter Rote , Gerhard Woeginger, Minimum-link paths among obstacles in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.63-72, June 07-09, 1990, Berkley, California, United States
	Alireza Zarei , Mohammad Ghodsi, Efficient computation of query point visibility in polygons with holes, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Binay Kumar Bhattacharya , Subir Kumar Ghosh , Thomas Caton Shermer, A linear time algorithm to remove winding of a simple polygon, Computational Geometry: Theory and Applications, v.33 n.3, p.165-173, February 2006
	Alireza Zarei , Mohammad Ghodsi, Query point visibility computation in polygons with holes, Computational Geometry: Theory and Applications, v.39 n.2, p.78-90, February, 2008
	P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany
	Pankaj K. Agarwal , David Brady , Jiří Matoušek, Segmenting object space by geometric reference structures, ACM Transactions on Sensor Networks (TOSN), v.2 n.4, p.455-465, November 2006
	Esther Moet , Christian Knauer , Marc van Kreveld, Visibility maps of segments and triangles in 3D, Computational Geometry: Theory and Applications, v.39 n.3, p.163-177, April, 2008
	Rajasekhar Inkulu , Sanjiv Kapoor, Visibility queries in a polygonal region, Computational Geometry: Theory and Applications, v.42 n.9, p.852-864, November, 2009