Constructing higher-dimensional convex hulls at logarithmic cost per face

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing higher-dimensional convex hulls at logarithmic cost per face

Full text

Pdf (766 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 404 - 413

Year of Publication: 1986

ISBN:0-89791-193-8

Author

R Seidel

Computer Science Department, Cornell University, Ithaca N.Y. and Digital Equipment Corporation Systems Research Center, Palo Alto, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 51, Citation Count: 38

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/12130.12172 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.

	BO	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	B	Bhattacharya, B. Application of Computational Geometry to Pattern Recognition Problems. Simon Fraser Univ. CS Tech.Rep. 82-3 (1982).
	B-M	Bruggesser, H. and Mani, P., Shellable Decompositions of Cells and Spheres. Math. Scand. 29 (1971), 197-205.
	D	Dyer, M.E., The Complexity of Vertex Enumeration Methods. Math. Oper. Res. 8 (1983), 381-402.
	Ga	Graham, R.L., An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Inform. Proc. Lett. 1 (1972), 132-133.
	K	Kallay, M., Convex Hull Algorithms for Higher Dimensions. Manuscript (1981).
	K-S	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]
	M-S	McMullen, P. and Shephard, G.C., Convex Polytopes and the Upper Bound Conjecture. London Math. Soc. Lecture Notes Series, vol 3, Cambridge Univ. Press (1971).
	M-R	Mattheiss, T.H. and Rubin, D.S., A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets. Math. Oper. Res. 5 (1980), 167-185.
	M	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	P-S	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	P-H	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]
	R-W	Rey, C. and Ward, R., An On-Line Algorithm for Determining Convex Polytopes. Manuscript, Dept. of EE, Univ. of B.C. (1984).
	S	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	Sw	Swart, G., Finding the Convex Hull Facet by Facet. J. of Algorithms 6 (1985), 17-48.
	Ya	Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]

CITED BY 38

	H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany
	K L Clarkson, Further applications of random sampling to computational geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.414-423, May 28-30, 1986, Berkeley, California, United States
	Nina Amenta , Günter M. Ziegler, Shadows and slices of polytopes, Proceedings of the twelfth annual symposium on Computational geometry, p.10-19, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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
	M. Pellegrini , P. Shor, Finding stabbing lines in 3-dimensional space, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.24-31, January 28-30, 1991, San Francisco, California, United States
	Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, On degeneracy in geometric computations, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.16-23, January 23-25, 1994, Arlington, Virginia, United States
	Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany
	B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States
	R. A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Proceedings of the fifth annual symposium on Computational geometry, p.326-333, June 05-07, 1989, Saarbruchen, West Germany
	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
	Tomonari Masada , Hiroshi Imai , Keiko Imai, Enumeration of regular triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.224-233, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States
	Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
	K. Mulmuley, Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.322-330, May 13-17, 1990, Baltimore, Maryland, United States
	Jeff Erickson, New lower bounds for convex hull problems in odd dimensions, Proceedings of the twelfth annual symposium on Computational geometry, p.1-9, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Marco Pellegrini, Stabbing and ray shooting in 3 dimensional space, Proceedings of the sixth annual symposium on Computational geometry, p.177-186, June 07-09, 1990, Berkley, California, United States
	Jonathan Richard Shewchuk, Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations, Proceedings of the sixteenth annual symposium on Computational geometry, p.350-359, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Olivier Devillers, On deletion in Delaunay triangulations, Proceedings of the fifteenth annual symposium on Computational geometry, p.181-188, June 13-16, 1999, Miami Beach, Florida, United States
	Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States
	David Avis , Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Proceedings of the seventh annual symposium on Computational geometry, p.98-104, June 10-12, 1991, North Conway, New Hampshire, 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
	C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996
	Li Zhang , Harish Devarajan , Julien Basch , Piotr Indyk, Probabilistic analysis for combinatorial functions of moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.442-444, 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
	Hervé Brönnimann , Timothy M. Chan , Eric Y. Chen, Towards in-place geometric algorithms and data structures, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	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
	Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States
	David Avis , David Bremner, How good are convex hull algorithms?, Proceedings of the eleventh annual symposium on Computational geometry, p.20-28, June 05-07, 1995, Vancouver, British Columbia, Canada
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Kurt Mehlhorn , Stefan Näher , Thomas Schilz , Stefan Schirra , Michael Seel , Raimund Seidel , Christian Uhrig, Checking geometric programs or verification of geometric structures, Proceedings of the twelfth annual symposium on Computational geometry, p.159-165, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Marc Van Kreveld , Iris Reinbacher , Avi Arampatzis , Roelof Van Zwol, Multi-Dimensional Scattered Ranking Methods for Geographic Information Retrieval*, Geoinformatica, v.9 n.1, p.61-84, March 2005
	Nina Amenta , Dominique Attali , Olivier Devillers, Complexity of Delaunay triangulation for points on lower-dimensional polyhedra, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1106-1113, January 07-09, 2007, New Orleans, Louisiana
	M. E. Gegúndez , J. Aroba , J. M. Bravo, Identification of piecewise affine systems by means of fuzzy clustering and competitive learning, Engineering Applications of Artificial Intelligence, v.21 n.8, p.1321-1329, December, 2008