Linear programming and convex hulls made easy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear programming and convex hulls made easy

Full text

Pdf (425 KB)

Source

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

Berkley, California, United States

Pages: 211 - 215

Year of Publication: 1990

ISBN:0-89791-362-0

Author

Raimund Seidel

Computer Science Division, University of California Berkeley, Berkeley CA

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): 14, Downloads (12 Months): 92, Citation Count: 39

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

ABSTRACT

We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time &Ogr;(m). The other constructs convex hulls of n points in Rd, d > 3, in expected time &Ogr;(n⌈d/2⌉). In both bounds d is considered to be a constant. In the linear programming algorithm the dependence of the time bound on d is of the form d!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.

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.

	CK	Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
	C1	K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
	C2	K.L. Clarkson, Las Vegas Algorithms for Linear and Integer Programming When the Dimension is Small, Manuscript, (Oct. 1989).
	CS	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]
	D	M.E. Dyer, Linear Algorithms for Two and Three- Variable Linear Programs, SIAM J. on Computing s (i 9s~) 3~-45.
	DF	M.E. Dyer and A.M. Frieze, A Randomized Algorithm for Fixed-Dimensional Linear Programming, Manuscript (I 987).
	E	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	G	R.L. Graham, An Efficient Algorithm for Construeting the Convex Hull of a Finite Planar Set, Inf. Proc. Letters 1 (1972) 13g-133.
	K	M. Kallay, Convex Hull Algorihms in Higher Dimensions, Manuscript (1981).
	M1	N. Megiddo, Linear-Time Algorithms for Linear Programming in R3 and Related Problems, SIAM J. on Computing 12 (1983) 759-776.
	M2	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]
	PH	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]
	S1	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	S2	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	Sw	G. Swart, Finding the Convex Hull Facet by Facet, Journal of Algorithms 6 (1985) 17-48.

CITED BY 39

	Jonathan Cohen , Dinesh Manocha , Marc Olano, Simplifying polygonal models using successive mappings, Proceedings of the 8th conference on Visualization '97, p.395-ff., October 18-24, 1997, Phoenix, Arizona, United States
	Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada
	Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991
	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States
	Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States
	Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, ACM SIGMOD Record, v.29 n.2, p.391-402, June 2000
	Nina Amenta, Finding a line transversal of axial objects in three dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.66-71, September 1992, Orlando, Florida, United States
	Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States
	Seth J. Teller, Computing the antipenumbra of an area light source, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.139-148, July 1992
	Michael E. Hohmeyer, A surface intersection algorithm based on loop detection, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.197-207, June 05-07, 1991, Austin, Texas, United States
	Franz Aurenhammer , Otfried Schwarzkopf, A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.142-151, June 10-12, 1991, North Conway, New Hampshire, United States
	Günter Rote, Degenerate convex hulls in high dimensions without extra storage, Proceedings of the eighth annual symposium on Computational geometry, p.26-32, June 10-12, 1992, Berlin, Germany
	Nina Amenta, Helly theorems and generalized linear programming, Proceedings of the ninth annual symposium on Computational geometry, p.63-72, May 18-21, 1993, San Diego, California, United States
	Binay K. Bhattacharya , Sreesh Jadhav , Asish Mukhopadhayay , Jean-Marc Robert, Optimal algorithms for some smallest intersection radius problems (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.81-88, June 10-12, 1991, North Conway, New Hampshire, United States
	S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996
	T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France
	Amitabh Varshney , Frederick P. Brooks, Jr. , William V. Wright, Interactive visualization of weighted three-dimensional alpha hulls, Proceedings of the tenth annual symposium on Computational geometry, p.395-396, June 06-08, 1994, Stony Brook, New York, United States
	Pankaj K. Agarwal , Pavan K. Desikan, An efficient algorithm for terrain simplification, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.139-147, January 05-07, 1997, New Orleans, Louisiana, United States
	Gokul Varadhan , Shankar Krishnan , Young J. Kim , Suhas Diggavi , Dinesh Manocha, Efficient max-norm distance computation and reliable voxelization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Amitabh Varshney , Frederick P. Brooks, Fast analytical computation of Richards's smooth molecular surface, Proceedings of the 4th conference on Visualization '93, October 25-29, 1993, San Jose, California
	Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Six-degree-of-freedom haptic rendering using incremental and localized computations, Presence: Teleoperators and Virtual Environments, v.12 n.3, p.277-295, 1 June 2003
	Young J. Kim , Ming C. Lin , Dinesh Manocha, Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.152-163, March 2004
	Shankar Krishnan , Dinesh Manocha, An efficient surface intersection algorithm based on lower-dimensional formulation, ACM Transactions on Graphics (TOG), v.16 n.1, p.74-106, Jan. 1997
	Shankar Krishnan , Atul Narkhede , Dinesh Manocha, Representation and computation of Boolean combinations of sculptured models, Proceedings of the eleventh annual symposium on Computational geometry, p.408-409, June 05-07, 1995, Vancouver, British Columbia, Canada
	Amitabh Varshney , Frederick P. Brooks, Jr. , William V. Wright, Computing Smooth Molecular Surfaces, IEEE Computer Graphics and Applications, v.14 n.5, p.19-25, September 1994
	Ronen Basri , David W. Jacobs, Projective Alignment with Regions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.5, p.519-527, May 2001
	David Jacobs , Ronen Basri, 3-D to 2-D Pose Determination with Regions, International Journal of Computer Vision, v.34 n.2-3, p.123-145, Nov. 1999
	Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Indexing the Solution Space: A New Technique for Nearest Neighbor Search in High-Dimensional Space, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.45-57, January 2000
	Mashhuda Glencross , Alan G. Chalmers , Ming C. Lin , Miguel A. Otaduy , Diego Gutierrez, Exploiting perception in high-fidelity virtual environments Additional presentations from the 24th course are available on the citation page , ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
	Umut A. Acar , Guy E. Blelloch , Matthias Blume , Kanat Tangwongsan, An experimental analysis of self-adjusting computation, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Miguel A. Otaduy , Ming C. Lin, Introduction to haptic rendering, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Qinglu Kong , Qiuming Zhu, Incremental procedures for partitioning highly intermixed multi-class datasets into hyper-spherical and hyper-ellipsoidal clusters, Data & Knowledge Engineering, v.63 n.2, p.457-477, November, 2007
	Mihael Ankerst , Bernhard Braunmüller , Hans-Peter Kriegel , Thomas Seidl, Improving Adaptable Similarity Query Processing by Using Approximations, Proceedings of the 24rd International Conference on Very Large Data Bases, p.206-217, August 24-27, 1998
	T. D. Alter , David W. Jacobs, Uncertainty Propagation in Model-Based Recognition, International Journal of Computer Vision, v.27 n.2, p.127-159, Mar 1998
	Mikola Lysenko, Realtime constructive solid geometry, ACM SIGGRAPH 2007 sketches, August 05-09, 2007, San Diego, California
	Mikola Lysenko, Realtime constructive solid geometry, ACM SIGGRAPH 2007 posters, August 05-09, 2007, San Diego, California
	Diego R. Llanos , David Orden , Belen Palop, New Scheduling Strategies for Randomized Incremental Algorithms in the Context of Speculative Parallelization, IEEE Transactions on Computers, v.56 n.6, p.839-852, June 2007
	Mikola Lysenko , Roshan D'Souza , Ching-Kuan Shene, Improved Binary Space Partition merging, Computer-Aided Design, v.40 n.12, p.1113-1120, December, 2008
	Hélia Pouyllau , Stefan Haar, End-to-end QoS of X-domain pipes, The Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness & Workshops, August 14-17, 2007, Vancouver, Canada