Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons

Full text

Pdf (1.08 MB)

Source

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

Miami Beach, Florida, United States

Pages: 227 - 236

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

Siu-Wing Cheng	Hong Kong University of Science & Technology, Dept. of Computer Science, Clear Water Bay, Kowloon, Hong Kong
Hazel Everett	Dép. d'informatique, Université du Québec à Montréal, C.p. 8888, Succursale Centre-Ville, Montréal, Canada H3C 3P8
Otfried Cheong	Hong Kong University of Science & Technology, Dept. of Computer Science, Clear Water Bay, Kowloon, Hong Kong
René van Oostrum	Universiteit Utrecht, Vakgroep Informatica, Postbus 80.089, 3508 TB Utrecht, Netherlands

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): 2, Downloads (12 Months): 11, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/304893.304976 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.

	1	Pankaj K. Agarwal , Micha Sharir, Circle shooting in a simple polygon, Journal of Algorithms, v.14 n.1, p.69-87, Jan. 1993 [doi>10.1006/jagm.1993.1004]
	2	P. K. Agarwal and M. Sharir. Circular visibility of a simple polygon from a fixed point. Internat. J. Comput. Geom. Appl., 3:1-25, March 1993.
	3	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
	4	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	5	B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algor#thmica, 1:133-162, 1986.
	6	B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163-191, 1986.
	7	B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
	8	B. Chazelle , J. Incerpi, Triangulation and shape-complexity, ACM Transactions on Graphics (TOG), v.3 n.2, p.135-152, April 1984 [doi>10.1145/357337.357340]
	9	David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
	10	A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
	11	Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
	12	Greg N. Frederickson, A data structure for dynamically maintaining rooted trees, Journal of Algorithms, v.24 n.1, p.37-65, July 1997 [doi>10.1006/jagm.1996.0835]
	13	L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
	14	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
	15	D. G. Kirkpatrick. Efficient computation of continuous skeletons. In Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., pages 18-27, 1979.
	16	D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12:28-35, 1983.

CITED BY 4

	Dan Halperin , Micha Sharir , Ken Goldberg, The 2-center problem with obstacles, Proceedings of the sixteenth annual symposium on Computational geometry, p.80-90, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Dan Halperin , Micha Sharir , Ken Goldberg, The 2-center problem with obstacles, Journal of Algorithms, v.42 n.1, p.109-134, January 2002
	Joachim Gudmundsson , Mikael Hammar , Marc van Kreveld, Higher order Delaunay triangulations, Computational Geometry: Theory and Applications, v.23 n.1, p.85-98, July 2002
	Vladlen Koltun, Segment intersection searching problems in general settings, Proceedings of the seventeenth annual symposium on Computational geometry, p.197-206, June 2001, Medford, Massachusetts, United States