A class of convex programs with applications to computational geometry

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A class of convex programs with applications to computational geometry

Full text

Pdf (504 KB)

Source

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

Berlin, Germany

Pages: 9 - 15

Year of Publication: 1992

ISBN:0-89791-517-8

Author

Martin Dyer

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): 29, Citation Count: 9

Additional Information:

abstract references cited by index terms

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

ABSTRACT

We consider the solution of convex programs in a small number of variables but large number of constraints, where all but a small number of the constraints are linear. We develop a general framework for obtaining algorithms for these problems which run in time linear in the number of constraints. We give an application to computing minimum spanning ellipsoids in fixed dimension.

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	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	2	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]
	3	K. L. Clarkson, "ALas Vegas algorithm for linear programming when the dimension is small", Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp 452-456.
	4	D. P. Dobkin and D. G. Kirkpatrick, "A linear algorithm for determining the separation of convex polyhedra", Journal of Algorithms 6 (1985), 381-393.
	5	M. E. Dyer, ':On a multidimcn~ionM ~c~rch procedure and its application to the Euclidean onecentre problem", SIAM Journal on Computing 13 (1984), 31-45.
	6	M. GrStschel, L. Lovg~z and A. Schrijvcr, Geometric algorithms and combinatorial optimization, Springer, Berlin, 1988.
	7	N. Jacobson, Basic algebra I (Second edition), Freeman, New York, 1985.
	8	N. Megiddo, "Linear programming in linear time when the dimension is fixed", SIAM Journal on Computing 12 (1983), 759-776.
	9	N. Megiddo, On the ball spanned by balls, Discrete & Computational Geometry, v.4 n.6, p.605-610, Sep. 1989 [doi>10.1007/BF02187750]
	10	M. Minoux, Mathematical programming-ih~o~?I and algorithms, Wiley, Chichester, 1986.
	11	Mark J. Post, Minimum spanning ellipsoids, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.108-116, December 1984 [doi>10.1145/800057.808672]
	12	J. Renegar, "A faster PSPACE algorithm for deciding the existential theory of the reals", Proc. ~gth IEEE Symposium on Foundations of Computer Science, 1988, pp 291-295.
	13	Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
	14	E. Welzl, "Smallest enclosing disks (balls and ellipsoids)'', to appear in New Results and New Trends in Computer Science, (H. Maurer, Ed.), Lecture Notes in Computer Science, 1991.

CITED BY 9

	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.478-484, May 16-18, 1993, San Diego, California, United States
	Timothy M. Chan, Deterministic algorithms for 2-d convex programming and 3-d online linear programming, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.464-472, January 05-07, 1997, New Orleans, Louisiana, United States
	Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany
	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
	Bernd Gärtner , Sven Schönherr, Exact primitives for smallest enclosing ellipses, Proceedings of the thirteenth annual symposium on Computational geometry, p.430-432, June 04-06, 1997, Nice, France
	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
	Kaspar Fischer , Bernd Gartner, The smallest enclosing ball of balls: combinatorial structure and algorithms, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998