A linear-time algorithm for triangulating simple polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A linear-time algorithm for triangulating simple polygons

Full text

Pdf (713 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 380 - 388

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

R E Tarjan	Department of Computer Science, Princeton University, Princeton, New Jersey and AT&T Bell Laboratories, Murray Hill, New Jersey
C J Van Wyk	AT&T Bell Laboratories, Murray Hill, New Jersey

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 45, Citation Count: 2

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/12130.12170 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	M.R. Brown and R. E. Tarjan, "Design and analysis of a data structure for representing sorted lists," SIAM J. Comput. 9, pp. 594-614 (1980).
	2	B. Chazelle, "A theorem on polygon cutting with applications," Prec. 23rd Annual Symp. on Foundations of Comput. Sci., pp. 339-349 (1982).
	3	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]
	4	D.P. Dobkin, D. L. Souvaine, and C. J. Van Wyk, Linear-time algorithms for splinegon problems, in preparation.
	5	H. Edelsbruner, L, J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision, Digital Equipment Corporation Systems Research Center Report #2, 1984.
	6	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]
	7	M.R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, "Triangulating a simple polygon," Inform. Prec. Left. 7(4), pp. 175-180 (1978).
	8	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]
	9	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
	10	Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E. Tarjan, Sorting Jordan sequences in linear time, Proceedings of the first annual symposium on Computational geometry, p.196-203, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323259]
	11	Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E Tarjan, Sorting Jordan sequences in linear time using level-linked search trees, Information and Control, v.68 n.1-3, p.170-184, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80033-X]
	12	S. Huddleston and K. Mehlhorn, "A new data structure for representing sorted lists," Acta Inform. 17, pp. 157-184 (1982).
	13	J .M . Keil, "Decomposing a polygon into simpler components," SIAM J. Comput. 14(4), pp. 799- 817 (1985).
	14	D. Maier and C. Salveter, "Hysterical B-trees," Inform. Prec. Lett. 12, pp. 199-202 (1981).
	15	K. Mehlhorn, Data Structures and Efficient Algorithms, Volume 1: Sorting and Searching, Springer-Verlag, Berlin (1984).
	16	Alejandro A. Schäffer , Christopher J. Van Wyk, Convex hulls of piecewise-smooth Jordan curves, Journal of Algorithms, v.8 n.1, p.66-94, March 1987 [doi>10.1016/0196-6774(87)90028-9]
	17	Diane Loring Souvaine, Computational geometry in a curved world (algorithm), 1986
	18	T .C . Woo and S. Y. Shin, "A linear time algorithm for triangulating a point-visible polygon," ACM Trans. on Graphics 4(1), pp. 60-69 (1985).

CITED BY 2

	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986
	Mingjie Lin , Yashar Ganjali, Power-efficient rate scheduling in wireless links using computational geometric algorithms, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada