Efficient plane sweeping in parallel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient plane sweeping in parallel

Full text

Pdf (1.02 MB)

Source

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

Yorktown Heights, New York, United States

Pages: 216 - 225

Year of Publication: 1986

ISBN:0-89791-194-6

Authors

M J Atallah	Department of Computer Sciences, Purdue University, West Lafayette, IN
M T Goodrich	Department of Computer Sciences, Purdue University, West Lafayette, IN

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): 8, Downloads (12 Months): 27, Citation Count: 5

Additional Information:

abstract 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/10515.10539 What is a DOI?

ABSTRACT

We present techniques which result in improved parallel algorithms for a number of problems whose efficient sequential algorithms use the plane-sweeping paradigm. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition, triangulation, and planar point location. Our technique can be used to improve on the previous time bound while keeping the space and processor bounds the same, or improve on the previous space bound while keeping the time and processor bounds the same. We also give efficient parallel algorithms for visibility from a point, 3-dimensional maxima, multiple range-counting, and rectilinear segment intersection counting. We never use the AKS sorting network in any of our algorithms.

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	A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dfinlaing, and C. Yap, gParallel Computational Geometry," Pro~. ~5th IEEE $~mp. Found. of Comp. $ci., 1985, 468--477.
	2	Mikhail J. Atallah , Michael T. Goodrich, Efficient parallel solutions to some geometric problems, Journal of Parallel and Distributed Computing, v.3 n.4, p.492-507, December 1, 1986 [doi>10.1016/0743-7315(86)90011-0]
	3	M.J. Agallah and M.T. Goodrich, gEfficient Plane Sweeping in Paranel," Purdue University Computer Science Tech. Report CSD-TR-56a, March 1986.
	4	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	5	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	6	B. Chazelle and J. Incerpi, "Triangulating a Polygon by Divide-and-Conquer," Proc. of ~1st Allerton Con/. on Comm. Control, and Comp., 1983, 447-456.
	7	Bernard Chaselle, Intersecting is easier than sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.125-134, December 1984 [doi>10.1145/800057.808674]
	8	B. Chazelle and L.J. Guibas, "Fractional Cascading: I. A Data Structuring Technique," manuscript.
	9	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	10	H. Edelsbrunner and M.H. Overmars, "On the Equivalence of Some Rectangle Problemsf Info. Proc. Letters, Vol. 14, No. 3, May 1982, 124-127.
	11	H. El Gindy and D. Avis, "A Linear Algorithm for Computing the Visibility Polygon from a Point," J. of Algorithms, Vol. 2, 1981, 186-197.
	12	M.T. Goodrich, "An Optimal Parallel Algorithm For the All Nearest-Neighbor Problem for a Convex Polygon," Purdue University Computer Science Tech. Report CSD-TR- 533, August 1985.
	13	D. Kirkpatrick, "Optimal Search in Planar Subdivision," SIAM Jour. on Comp., Vol. 12, No. 1, Feb. 1983, 28-35.
	14	C. Kruskal, L. Rudolph, and M. Snir, "The Power of Parallel Prefix,~ Proc. 1985 Int. Conf. on Parallel Proc., 180-185.
	15	H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
	16	D.T. Lee and F.P. Preparata, ~Computational Geometry-- A Survey," IEEE Trans. on Computers, Vol. C-33, No. 12, December 1984, 872-1101.
	17	G. Lueker and D. Willard, "A Data Structure for Dynamic Range Queriesf lnfo. Proc. Letters, Vol. 15, No. 5, Decembet 1982, 209-213.
	18	M.H. Overmars and J. Van Leeuwen, "Maintenance of Configurations in the Plane," Jour. of Cornp. and Sys. Sci., Vol. 23, 1981, 166-204.
	19	M. Shamos and D. Hoey, "Geometric Intersection Problems," Proc. 17th iEEE S~lrnp. Found. of Comp. Sci., 1976, 208-215.
	20	L. Valiant, "Parallelism in Comparison Problems,~ SIAM Jour. on Cornp., Vol. 4, No. 3, Sept. 1975, 348-355.

CITED BY 5

	Haklin Kimm, Two dimensional maximal elements problem on a reconfigurable optical pipelined bus system, Proceedings of the 1998 ACM symposium on Applied Computing, p.623-627, February 27-March 01, 1998, Atlanta, Georgia, United States
	N. Dadoun , D. G. Kirkpatrick, Parallel processing for efficient subdivision search, Proceedings of the third annual symposium on Computational geometry, p.205-214, June 08-10, 1987, Waterloo, Ontario, Canada
	Shashi Shekhar , Sivakumar Ravada , Vipin Kumar , Douglas Chubb , Greg Turner, Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems, IEEE Transactions on Knowledge and Data Engineering, v.10 n.4, p.632-655, July 1998
	V. Yugandhar , Sanjeev Saxena, Parallel algorithms for separable permutations, Discrete Applied Mathematics, v.146 n.3, p.343-364, 15 March 2005
	Sanjeev Saxena, Dominance made simple, Information Processing Letters, v.109 n.9, p.419-421, April, 2009