Planar separators and parallel polygon triangulation (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Planar separators and parallel polygon triangulation (preliminary version)

Full text

Pdf (999 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 507 - 516

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Michael T. Goodrich

Dept. of Computer Science, The Hopkins University, Baltimore, MD

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, Citation Count: 10

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/129712.129762 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	Richard J. Anderson , Gary L. Miller, Deterministic Parallel List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.81-90, June 28-July 01, 1988
	2	J.L. Bentley and D. Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. on Computers, C- 29(7), 1980, 571-576.
	3	S.N. Bhatt and F.T. Leighton, "A Framework fo# Solving VLSI Graph Layout Problems," J. Comp. and Sys. Sci., 28(2), 1984, 300-343.
	4	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	5	B. Chuelle, "A Theorem on Polygon Cutting with Applications," #3rd FOCS, 1982, 339-349.
	6	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	7	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 [doi>10.1145/109648.109665]
	8	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	9	Richard Cole , Uzi Vishkin, Approximate parallel scheduling. Part I: the basic technique with applications to optimal parallel list ranking in logarithmic time, SIAM Journal on Computing, v.17 n.1, p.128-142, Feb. 1988 [doi>10.1137/0217009]
	10	R. Cole and U. Vishkin, "The Accelerated Centroid Decomposition Technique for Optimal Paxallel Tree Evaluation in Logarithmic Time," Algorithmica, 3, 1988, 329-346.
	11	Richard Cole , Ofer Zajicek, An optimal parallel algorithm for building a data structure for planar point location, Journal of Parallel and Distributed Computing, v.8 n.3, p.280-285, Mar. 1990 [doi>10.1016/0743-7315(90)90103-V]
	12	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	13	M.R. Garey, D.S. Johnson, F.P. Prepsrata, and R.E. Taxjan, "Triangulating s Simple Polygon," IPL, T(4), 1978, 175-179.
	14	H. Gazit and G.L. Miller, "A Parallel Algorithm for Finding s Separator in Planar Graphs," #Sth FOCS, 1987, 238-248.
	15	M. T. Goodrich, Triangulating a polygon in parallel, Journal of Algorithms, v.10 n.3, p.327-351, September 1989 [doi>10.1016/0196-6774(89)90032-1]
	16	Michael T. Goodrich , Steven B. Shauck , Sumanta Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), Proceedings of the sixth annual symposium on Computational geometry, p.73-82, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98539]
	17	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
	18	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]
	19	C. Kruskal, L. Rudolph, and M. Snip, "The Power of Paxailel Prefix," Proc. 1985 IEEE Int. Conf. on Parallel Proc., 180-185.
	20	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	21	R.J. Lipton and R.E. Tsrjan, "A Separator Theorem for Planar Graphs," SIAM 3. Appl. Math., 36(2), 1979, 177-189.
	22	R.J. Lipton and R.E. Tarjan, "Applications of a Planar Separator Theorem," SIAM 3. Comput., 9(3), 1980, 615-627.
	23	Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
	24	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	25	C.K. Yap, "Parallel Triangulation of a Polygon in Two Calls to the Tmpezoided Map,# Algorithmica, 3, 1988, 279-288.

CITED BY 10

	David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003
	Danny Z. Chen, An optimal parallel algorithm for detecting weak visibility of a simple polygon, Proceedings of the eighth annual symposium on Computational geometry, p.63-72, June 10-12, 1992, Berlin, Germany
	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
	Greg N. Frederickson, A data structure for dynamically maintaining rooted trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.175-184, January 25-27, 1993, Austin, Texas, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada
	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
	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification for dynamic planar graph algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.208-217, May 16-18, 1993, San Diego, California, United States
	Mikhail J. Atallah , Keith B. Frikken , Marina Blanton, Dynamic and efficient key management for access hierarchies, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Lyudmil Aleksandrov , Hristo Djidjev , Hua Guo , Anil Maheshwari, Partitioning planar graphs with costs and weights, Journal of Experimental Algorithmics (JEA), 11, 2006