Triangulation and shape-complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Triangulation and shape-complexity

Full text

Pdf (1.14 MB)

Source

ACM Transactions on Graphics (TOG) archive
Volume 3 , Issue 2 (April 1984) table of contents

Pages: 135 - 152

Year of Publication: 1984

ISSN:0730-0301

Authors

B. Chazelle	Department of Computer Science, Brown University, Providence, RI
J. Incerpi	Department of Computer Science, Brown University, Providence, RI

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 42, Citation Count: 13

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/357337.357340 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	CHAZELLE, B. A theorem on polygon-cutting with applications. In Proceedings o{ the 23rd IEEE Annual Symposium on Foundations of Computer Science, (Chicago, Nov. 3-5 1982). IEEE, New York, pp. 339-349.
	2	GAREY, M. R., JOHNSON, D. S., PREPARATA, F. P. AND TARJAN, R.E. Triangulating a simple polygon, inf. Proc. Lett. 7, 4 (June 1978), 175-180.
	3	Leo J. Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.221-234, December 1983 [doi>10.1145/800061.808751]
	4	Stefan Hertel , Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.207-218, August 21-27, 1983
	5	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	6	Michael Ian Shamos, Computational geometry., 1978
	7	SCHOONE, A. A., AND VAN LEEUWEN, J. Triangulating a star-shaped polygon. Tech. Rep. RUV- CS-80-3, Univ. of Utrecht, April 1980.
	8	TOUSSAINT, G.T. Pattern recognition and geometrical complexity. In Proceedings of the 5th International Conference on Pattern Recognition (Dec. 1980), pp. 1324-1347.
	9	TOUSSAINT, G. W., AND AVIS, D. On a convex hull algorithm for polygons and its application to triangulation problems. Pattern Recog. 15, 1 (1982) 23-29.

CITED BY 13

	David G. Kirkpatrick , Maria M. Klawe , Robert E. Tarjan, Polygon triangulation in O(n log log n) time with simple data-structures, Proceedings of the sixth annual symposium on Computational geometry, p.34-43, June 07-09, 1990, Berkley, California, United States
	Siu-Wing Cheng , Hazel Everett , Otfried Cheong , René van Oostrum, Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons, Proceedings of the fifteenth annual symposium on Computational geometry, p.227-236, June 13-16, 1999, Miami Beach, Florida, United States
	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Linear-time triangulation of a simple polygon made easier via randomization, Proceedings of the sixteenth annual symposium on Computational geometry, p.201-212, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Michael Goldwasser, An implementation for maintaining arrangements of polygons, Proceedings of the eleventh annual symposium on Computational geometry, p.432-433, June 05-07, 1995, Vancouver, British Columbia, Canada
	J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size, Proceedings of the third annual symposium on Computational geometry, p.11-20, June 08-10, 1987, Waterloo, Ontario, Canada
	R E Tarjan , C J Van Wyk, A linear-time algorithm for triangulating simple polygons, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.380-388, May 28-30, 1986, Berkeley, California, United States
	David Meyers , Shelley Skinner , Kenneth Sloan, Surfaces from contours, ACM Transactions on Graphics (TOG), v.11 n.3, p.228-258, July 1992
	K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Proceedings of the fourth annual symposium on Computational geometry, p.18-22, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Leonidas J. Guibas , Rajeev Motwani , Prabhakar Raghavan, The robot localization problem in two dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.259-268, September 1992, Orlando, Florida, United States
	Kenneth L. Clarkson , Richard Cole , Robert E. Tarjan, Randomized parallel algorithms for trapezoidal diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.152-161, June 10-12, 1991, North Conway, New Hampshire, United States
	Gian Paolo Lorenzetto , Amitava Datta, An almost linear-time algorithm for trapezoidation of GIS polygons, Future Generation Computer Systems, v.20 n.7, p.1145-1155, October 2004
	Menelaos I. Karavelas, Guarding curvilinear art galleries with edge or mobile guards, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Menelaos I. Karavelas , Csaba D. Tóth , Elias P. Tsigaridas, Guarding curvilinear art galleries with vertex or point guards, Computational Geometry: Theory and Applications, v.42 n.6-7, p.522-535, August, 2009