Faster output-sensitive parallel convex hulls for d≤3

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Faster output-sensitive parallel convex hulls for d≤3: optimal sublogarithmic algorithms for small outputs

Full text

Pdf (1.00 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 176 - 185

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Neelima Gupta	Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi 110016, India
Sandeep Sen	Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi 110016, India

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): 4, Downloads (12 Months): 21, 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/237218.237351 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	A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap. Parallel computational geometry. Proc. of 25th Annual Symposium on Foundations of Computer Science, pages 468 - 477, 1985. also appears in full version in Algorithmica, Vol. 3, No. 3, 1988, pp. 293- 327.
	2	N.M. Amato, M.T. Goodrich and E.A. Ramos. Parallel Algorithms for Higher-Dimensional Convex Hulls. Proc. of the 35th Annual Foes, pages 683-694, 1994.
	3	S G. Akl, Optimal parallel algorithms for computing convex hulls and for sortng, Computing, v.33 n.1, p.1-11, 1984 [doi>10.1007/BF02243071]
	4	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]
	5	M.J. Atallah and M.T. Goodrich. Parallel algorithm for some functions of two convex polygons. Algorithmica, 3(4):535- 548, 1988.
	6	N.M. Amato and F.P. Preparata. The Parallel 3D convex hull problem revisited. Internat. JI. Comput. Geom. AppI., 2(2):163-173, 1992.
	7	H Bast and T Hagerup. Fast parallel space allocation,estimation and integer sorting. Technical Report, MPLI-93-123, June 1993.
	8	B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
	9	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	10	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220281]
	11	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	12	B Chazelle and J Fredman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990.
	13	B. Chazelle and J. Matousek. Derandomizing an output-sensitive convex-hull algorithm in three dimensions. Tech. Rept., Princeton University, 1992.
	14	Richard John Cole, An optimally efficient selection algorithm, Information Processing Letters, v.26 n.6, p.295-299, January 25, 1988 [doi>10.1016/0020-0190(88)90186-X]
	15	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]
	16	X. Deng, An optimal parallel algorithm for linear programming in the plane, Information Processing Letters, v.35 n.4, p.213-217, Aug. 1990 [doi>10.1016/0020-0190(90)90026-T]
	17	N. Dadoun , D. G. Kirkpatrick, Parallel construction of subdivision hierarchies, Journal of Computer and System Sciences, v.39 n.2, p.153-165, Oct. 1989 [doi>10.1016/0022-0000(89)90042-1]
	18	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	19	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113397]
	20	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
	21	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	22	R L Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Proc. Lett., 1:132-133, 1972.
	23	Torben Hagerup, Fast deterministic processor allocation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.1-10, January 25-27, 1993, Austin, Texas, United States
	24	T. Hagerup and R. Raman. Waste makes haste: Tight bounds for loose, parallel sorting. Proc. of the 33rd Annual FOGS, pages 628-637, 1992.
	25	D. Haussler and E. Welzl. e-Nets and simplex range queries. Discrete and Computational Geometry, 2, 1987, pp. 127-152.
	26	Optimal deterministic approximate parallel prefix sums and their applications, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.220, January 04-06, 1995
	27	S. Kapoor and P. Ramanan. Lower bounds for maximal and convex layer problems. Algorithmica, pages 447-459, 1989.
	28	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	29	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	30	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	31	F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
	32	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	33	John H. Reif , Sandeep Sen, Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.21 n.3, p.466-485, June 1992 [doi>10.1137/0221031]
	34	S. Rajasekaran and S. Sen. Random sampling Techn,ques and parallel algorithm design. J.H. Reif editor. Morgan, Kaufman Publishers, 1993.
	35	John H. Reif , Sandeep Sen, Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications, SIAM Journal on Computing, v.23 n.3, p.633-651, June 1994 [doi>10.1137/S0097539790184298]
	36	Sandeep Sen, Lower Bounds for Parallel Algebraic Decision Trees, Complexity of Convex Hulls and Related Problems, Proceedings of the 14th Conference on Foundations of Software Technology and Theoretical Computer Science, p.193-204, December 15-17, 1994
	37	S. Sen. Parallel multidimensional search using approximation algorithms: with applications to linearprogramming and related problems, unpublished manuscript, 1995.
	38	Michael Ian Shamos, Computational geometry., 1978

CITED BY 2

	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003