Minimum spanning ellipsoids

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimum spanning ellipsoids

Full text

Pdf (474 KB)

Source

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

Pages: 108 - 116

Year of Publication: 1984

ISBN:0-89791-133-4

Author

Mark J. Post

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 7

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

ABSTRACT

The notion of a minimum spanning ellipsoid in any dimension is explained. Basic definitions and theorems provide the ideas for an algorithm to find the minimum spanning ellipsoid of a set of points, i.e., the ellipsoid of minimum volume containing the set. The run-time of the algorithm O (n2) independent of dimension, where n is the number of points.

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	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]
	2	D.P. Dobkin and S.P. Reiss, The Complexity of Linear Programming, Theoretical Computer Science, 11, (1980), pp. 1-18.
	3	James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	4	P. Gacs and L. Lovasz, Khachian's Algorithm for Linear Programming, Computer Science Department, Stanford University, 1979.
	5	B. Grünbaum, Convex Polytopes, Interscience Publishers, London, 1967.
	6	P. Halmos, Finite Dimensionl Vector Spaces, Springer-Verlag, New York, 1974.
	7	Marhall, A.W., and Olkin, I., Inequalities: Theory of Majorization and Its Applications, Academic Press, Inc., New York, 1979.
	8	M. Post, A Minimum Spanning Ellipse Algorithm, Proc. 22nd IEEE Symposium on Foundations of Computer Science, October 1981.
	9	M. Post, Computing Minimum Spanning Ellipses, Brown University Technical Report No. CS-82-16 Providence, May 1982.
	10	Mark J. Post, Ellipsoids and computational geometry, 1985
	11	Michael Ian Shamos, Computational geometry., 1978

CITED BY 7

	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 , 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
	Martin Dyer, A class of convex programs with applications to computational geometry, Proceedings of the eighth annual symposium on Computational geometry, p.9-15, June 10-12, 1992, Berlin, Germany
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	P. L. Lin , W. H. Tan, An efficient method for the retrieval of objects by topological relations in spatial database systems, Information Processing and Management: an International Journal, v.39 n.4, p.543-559, July 2003
	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
	Elon Rimon , Stephen P. Boyd, Obstacle Collision Detection Using Best Ellipsoid Fit, Journal of Intelligent and Robotic Systems, v.18 n.2, p.105-126, February 1997