An efficient, exact, and generic quadratic programming solver for geometric optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient, exact, and generic quadratic programming solver for geometric optimization

Full text

Pdf (825 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 110 - 118

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Bernd Gärtner	Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland
Sven Schönherr	Institut für Informatik, Freie Universität Berlin, Takustr. 9, D-14195 Berlin, Germany and Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland

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): 6, Downloads (12 Months): 34, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/336154.336191 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	Pankaj K. Agarwal , Boris Aronov , Sariel Har-Peled , Micha Sharir, Approximation and exact algorithms for minimum-width annuli and shells, Proceedings of the fifteenth annual symposium on Computational geometry, p.380-389, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304992]
	2	V. Chv~tal. Linear Programming. W. H. Freeman, New York, NY, 1983.
	3	Andreas Fabri , Geert-Jan Giezeman , Lutz Kettner , Stefan Schirra , Sven Schönherr, On the design of CGAL a computational geometry algorithms library, Software—Practice & Experience, v.30 n.11, p.1167-1202, Sept. 2000 [doi>10.1002/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B]
	4	Bernd Gärtner, Exact arithmetic at low cost—a case study in linear programming, Computational Geometry: Theory and Applications, v.13 n.2, p.121-139, June 1999 [doi>10.1016/S0925-7721(99)00012-7]
	5	Bernd Gärtner, Fast and Robust Smallest Enclosing Balls, Proceedings of the 7th Annual European Symposium on Algorithms, p.325-338, July 16-18, 1999
	6	Bernd Gärtner, Pitfalls in computing with pseudorandom determinants, Proceedings of the sixteenth annual symposium on Computational geometry, p.148-155, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336195]
	7	Bernd Gärtner , Emo Welzl, Random sampling in geometric optimization: new insights and applications, Proceedings of the sixteenth annual symposium on Computational geometry, p.91-99, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336186]
	8	Ravi Kumar , D. Sivakumar, Roundness estimation via random sampling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.603-612, January 17-19, 1999, Baltimore, Maryland, United States
	9	J. Matou~ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498-516, 1996.
	10	K. Mehlhorn, S. N~iher, M. Seel, and C. Uhrig. The LEDA User Manual, 1999. Version 4.0.
	11	David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
	12	A. L. Peressini , Francis E. Sullivan , J. J. Uhl, Jr., The mathematics of nonlinear programming, Springer-Verlag New York, Inc., New York, NY, 1988
	13	Kazuyuki Sekitani , Yoshitsugu Yamamoto, A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes, Mathematical Programming: Series A and B, v.61 n.2, p.233-249, Sept. 3, 1993 [doi>10.1007/BF01582149]
	14	The CGAL Consortium. The CGAL Reference Manual, 2000. Version 2.1.
	15	E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and Ne Trends in Computer Science, volume 555 of Lecture Notes Comput. Sci., pages 359-370. Springer-Verlag, 1991.
	16	P. Wolfe. The simplex method for quadratic programming. Econometrica, 27:382-398, 1959.
	17	P. Wolfe. Finding the nearest point in a polytope. Math. Programming, 11:128-149, 1976.

CITED BY 4

	Bernd Gärtner , Emo Welzl, Explicit and implicit enforcing: randomized optimization, Computational Discrete Mathematics: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	M. Pellegrini, Randomizing combinatorial algorithms for linear programming when the dimension is moderately high, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.101-108, January 07-09, 2001, Washington, D.C., United States
	Bernd Gärtner , Emo Welzl, Random sampling in geometric optimization: new insights and applications, Proceedings of the sixteenth annual symposium on Computational geometry, p.91-99, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Piyush Kumar , Joseph S. B. Mitchell , E. Alper Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, Journal of Experimental Algorithmics (JEA), 8, 2003