Linear-time triangulation of a simple polygon made easier via randomization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear-time triangulation of a simple polygon made easier via randomization

Full text

Pdf (1.04 MB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 201 - 212

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Nancy M. Amato	Texas A&M University, College Station, TX
Michael T. Goodrich	The Johns Hopkins University, Baltimore, MD
Edgar A. Ramos	Max-Planck-Institut für Informatik, Saarbrücken, Germany

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): 6, Downloads (12 Months): 40, Citation Count: 3

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/336154.336206 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 , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
	2	Takao Asano , Tetsuo Asano , Roy Y Pinter, Polygon triangulation: efficiency and minimality, Journal of Algorithms, v.7 n.2, p.221-231, June 1986 [doi>10.1016/0196-6774(86)90005-2]
	3	B. G. Baumgart. A polyhedron representation for computer vision. In Proc. AFIPS Natl. Comput. Conf., volume 44, pages 589-596. AFIPS Press, Alrington, Va., 1975.
	4	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	5	B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990.
	6	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]
	7	K. L. Clarkson, R. Cole, and R. E. Tarjan. Erratum: Randomized parallel algorithms for trapezoidal diagrams. Internat. J. Comput. Geom. Appl., 2(3):341-343, 1992.
	8	K. L. Clarkson, R. Cole, and R. E. Tarjan. Randomized parallel algorithms for trapezoidal diagrams. Internat. J. Comput. Geom. Appl., 2(2):117-133, 1992.
	9	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	10	K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Discrete & Computational Geometry, v.4 n.5, p.423-432, 1989 [doi>10.1007/BF02187741]
	11	M. de Berg, K. Dobrindt, and O. Schwarzkopfi On lazy randomized incremental construction. Discrete Comput. Geom., 14:261-286, 1995.
	12	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	13	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	14	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]
	15	M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Inform. Process. Lett., 7(4):175-179, 1978.
	16	Michael T. Goodrich, Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, v.51 n.3, p.374-389, Dec. 1995 [doi>10.1006/jcss.1995.1076]
	17	Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
	18	L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
	19	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	20	J. Hershberger. Optimal parallel algorithms for triangulated simple polygons, lnternat. J. Comput. Geom. Appl., 5:145-170, 1995.
	21	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 [doi>10.1145/98524.98533]
	22	Jiří Matoušek, Derandomization in computational geometry, Journal of Algorithms, v.20 n.3, p.545-580, May 1996 [doi>10.1006/jagm.1996.0027]
	23	K. Mulmuley, A fast planar partition algorithm, I, Journal of Symbolic Computation, v.10 n.3-4, p.253-280, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80064-8]
	24	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, N J, 1993.
	25	F.P. Preparata. A new approach to planar point location. SIAM J. Comput., 10(3):473-482, 1981.
	26	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	27	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 [doi>10.1145/6138.6151]
	28	Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
	29	R. Seidel. On the exact query complexity of planar point location. In Abstracts 14th European Workshop Comput. Geom., pages 7-8, 1998.
	30	Robert E. Tarjan , Christopher J. VanWyk, Erratum: an O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.5, p.1061-1061, October 1988 [doi>10.1137/0217067]
	31	C. K. Yap. Parallel triangulation of a polygon in two calls to the trapezoidal map. Algorithmica, 3:279-288, 1988.
	32	Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme, Journal of Computer and System Sciences, v.40 n.1, p.2-18, February 1990 [doi>10.1016/0022-0000(90)90016-E]
	33	C.-K. Yap, Symbolic treatment of geometric degeneracies, Journal of Symbolic Computation, v.10 n.3-4, p.349-370, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80069-7]

CITED BY 3

	Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001
	Jyh-Ming Lien , Nancy M. Amato, Approximate convex decomposition of polygons, Computational Geometry: Theory and Applications, v.35 n.1, p.100-123, August 2006
	Bernard Chazelle , Wolfgang Mulzer, Computing hereditary convex structures, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark