Triangulating Simple Polygons and Equivalent Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Triangulating Simple Polygons and Equivalent Problems

Full text

Pdf (1.11 MB)

Source

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

Pages: 153 - 174

Year of Publication: 1984

ISSN:0730-0301

Authors

A. Fournier	Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4
D. Y. Montuno	Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 183, Citation Count: 25

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.357341 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	ASANO, T., AND ASANO, T. Minimum partition of polygonal regions into trapezoids. In Proceedings o/the 24th Annual Symposium on the Foundations of Computer Science (Tucson, Az, Nov 7-9), IEEE, Los Angeles, 1983, pp. 233-241.
	2	Avis, D., AND TOUSSAINT, G.T. An efficient algorithm for decomposing a polygon into starshaped polygons. Pattern Recogn. 13, 6 (1981), 395-398.
	3	Bernard Chazelle , David Dobkin, Decomposing a polygon into its convex parts, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.38-48, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804396]
	4	CHVATAL, V. A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18 (1975), 39-41.
	5	EL GINDY, H., AND AVIS, D. A linear algorithm for computing the visibility polygon from a point. J. of Algo. 2, 4 (June 1981), 186-197.
	6	FENG, H., AND PAVLIDIS, T. Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition. IEEE Trans. Comput. C-24 (June 1975), 636-650.
	7	Eugene Fiume , Alain Fournier , Larry Rudolph, A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultracomputer, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.141-150, July 1983
	8	James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	9	FUCHS, H., POULTON, PAETH, A., AND BELL, A. Developing PIXEL-PLANES, a smart memorybased raster graphics system. In 1982 Conference on Advanced Research in VLSI. MIT Press, Boston, Mass. 1982, pp. 137-146.
	10	FUSSELL, D., AND RATHI, B.D. A VLSI-oriented architecture for real-time raster display of shaded polygons. In Proceedings of Graphics Interface '82, National Research Council of Canada, (Toronto, Ontario, May 17-21), 1982, pp. 373-380.
	11	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-179.
	12	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
	13	KEIL, J. M. Decomposing polygons into simpler components. Tech. Rep. 163/83. Dept. of Computer Science, Univ. of Toronto, 1983.
	14	KIRKPATRICK, D.G. Optimal search in planar subdivisions. SIAM J. Comput. 12, 1 (Feb. 1983), 28-35.
	15	D. T. Lee, Shading of regions on vector display devises, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.37-44, August 1981
	16	D. T. Lee , F. P. Preparata, An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM (JACM), v.26 n.3, p.415-421, july 1979 [doi>10.1145/322139.322142]
	17	Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
	18	LLOYD, E.L. On triangulations of a set of points in the plane. In Proceedings of the 18th Annual Symposium on the Foundation of Computer Science (Providence, RI, Oct. 31-Nov 2), IEEE, Los Angeles, 1977, pp. 228-240.
	19	MEISTERS, G.H. Polygons have ears. Amer. Math. Monthly 82 (1975), 648-651.
	20	PREPARATA, F. P. AND SUPOWIT, K. Testing a simple polygon for monotonicity. Inf. Proc. Lett. 12, 4 (Aug. 1981), 161-164.
	21	SCHACHTER, B. Decomposition of polygons into convex sets. IEEE Trans. Comput. C-27, 11 (Nov. 1978), 1078-1082.
	22	SCHOONE, A. A. AND VAN LEEUWEN, J. Triangulating a star-shaped polygon. Tech. Rep. RUV- CS-80-3, Univ. of Utrecht, Holland 1980.
	23	Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
	24	WATKINS, G.S. A real-time visible surface algorithm. Tech. Rep. UTEC-CSc-70-101, Computer Science Dept., Univ. of Utah 1970, NTIS AD-762 004.

CITED BY 25

	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
	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
	C Wang , E P F Chan, Finding the minimum visible vertex distance between two non-intersecting simple polygons, Proceedings of the second annual symposium on Computational geometry, p.34-42, June 02-04, 1986, Yorktown Heights, New York, United States
	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
	Elefterios A. Melissaratos , Diane L. Souvaine, On solving geometric optimization problems using shortest paths, Proceedings of the sixth annual symposium on Computational geometry, p.350-359, June 07-09, 1990, Berkley, California, United States
	Mario A. Lopez , Ravi Janardan , Sartaj Sahni, A fast algorithm for VLSI net extraction, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.770-774, November 07-11, 1993, Santa Clara, California, United States
	Bradley A. Payne , Arthur W. Toga, Surface Reconstruction by Multiaxial Triangulation, IEEE Computer Graphics and Applications, v.14 n.6, p.28-35, November 1994
	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
	Peter Epstein , Jörg-Rüdiger Sack, Generating triangulations at random, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.267-278, July 1994
	David Meyers , Shelley Skinner , Kenneth Sloan, Surfaces from contours, ACM Transactions on Graphics (TOG), v.11 n.3, p.228-258, July 1992
	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
	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
	Philippe Rigaux , Michel Scholl , Luc Segoufin , Stéphane Grumbach, Building a constraint-based spatial database system: model, languages, and implementation, Information Systems, v.28 n.6, p.563-595, September 2003
	Danny Z. Chen, Efficient Geometric Algorithms on the EREW PRAM, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.41-47, January 1995
	Lori Scarlatos , The Pavlidis, Hierarchical triangulation using terrain features, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	J. Friedman , J. Hershberger , J. Snoeyink, Compliant motion in a simple polygon, Proceedings of the fifth annual symposium on Computational geometry, p.175-186, June 05-07, 1989, Saarbruchen, West Germany
	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
	Jurek Czyzowicz , Peter Egyed , Hazel Everett , David Rappaport , Thomas Shermer , Diane Souvaine , Godfried Toussaint , Jorge Urrutia, The Aquarium Keeper's Problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.459-464, January 28-30, 1991, San Francisco, California, 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
	Peter D. Holmes , Erland R. A. Jungert, Symbolic and Geometric Connectivity Graph Methods for Route Planning in Digitized Maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.5, p.549-565, May 1992
	Jiqi Zhang , Hau-San Wong , Zhiwen Yu, 3D model metrieval based on volumetric extended gaussian image and hierarchical self organizing map, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
	Jinghua Zhang , Jinsheng Xu, Optimizing octree motion representation for 3D animation, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Jinghua Zhang , Charles B. Owen, Technical Section: Octree-based animated geometry compression, Computers and Graphics, v.31 n.3, p.463-479, June, 2007
	Chuan-Kai Yang , Wei-Ting Chiang, An interactive facial expression generation system, Multimedia Tools and Applications, v.40 n.1, p.41-60, October 2008
	Martin Held , Joseph S. B. Mitchell, Triangulating input-constrained planar point sets, Information Processing Letters, v.109 n.1, p.54-56, December, 2008