Smaller core-sets for balls

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Smaller core-sets for balls

Full text

Pdf (192 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 12A table of contents

Pages: 801 - 802

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

Mihai Bâdoiu	MIT Laboratory for Computer Science; Cambridge, Massachusetts
Kenneth L. Clarkson	Bell Labs; Murray Hill, New Jersey

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 58, Citation Count: 17

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Given a set of points P ⊂ R^d and value ∊ > 0, an ∊-core-set S ⊂ P has the property that the smallest ball containing S is an ∊-approximation of the smallest ball containing P. This paper shows that any point-set has an ∊-core-set of size [2/∊]. We also give a fast algorithm that finds this core-set. These results imply the existence of small core-sets for solving approximate k-center clustering and related problems. The sizes of these core-sets are considerably smaller than the previously known bounds, and imply faster algorithms; one such algorithm needs O(dn/∊ + (l/∊)⁵) time to compute an ∊-approximate minimum enclosing ball (1-center) of n points in d dimensions. A simple gradient-descent algorithm is also given, for computing the minimum enclosing ball in O(dn/∊²) time. This algorithm also implies slightly faster algorithms for computing approximately the smallest radius k-flat fitting a set 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	Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
	2	Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
	3	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	4	{KMA} Piyush Kumar, Joseph S. B. Mitchell and Alper Yildirim, Computing Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions. manuscript, 2002.

CITED BY 17

	Jie Gao , Michael Langberg , Leonard J. Schulman, Analysis of incomplete data and an intrinsic-dimension Helly theorem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.464-473, January 22-26, 2006, Miami, Florida
	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
	Hai Yu , Pankaj K. Agarwal , Raghunath Poreddy , Kasturi R. Varadarajan, Practical methods for shape fitting and kinetic data structures using core sets, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004
	Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Self-improving algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.261-270, January 22-26, 2006, Miami, Florida
	Yulai Xie , Jack Snoeyink , Jinhui Xu, Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Timothy M. Chan, Faster core-set constructions and data-stream algorithms in fixed dimensions, Computational Geometry: Theory and Applications, v.35 n.1, p.20-35, August 2006
	Mihai Bădoiu , Kenneth L. Clarkson, Optimal core-sets for balls, Computational Geometry: Theory and Applications, v.40 n.1, p.14-22, May, 2008
	Gereon Frahling , Christian Sohler, A fast k-means implementation using coresets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Frank Nielsen , Richard Nock, On approximating the smallest enclosing Bregman Balls, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Embeddings of surfaces, curves, and moving points in euclidean space, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Bernd Gärtner , Martin Jaggi, Coresets for polytope distance, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Kenneth L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.922-931, January 20-22, 2008, San Francisco, California
	Anirban Dasgupta , Petros Drineas , Boulos Harb , Ravi Kumar , Michael W. Mahoney, Sampling algorithms and coresets for ℓ_p regression, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.932-941, January 20-22, 2008, San Francisco, California
	Michael J. Todd , E. Alper Yıldırım, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, Discrete Applied Mathematics, v.155 n.13, p.1731-1744, August, 2007
	Guang Xu , Jinhui Xu, Efficient approximation algorithms for clustering point-sets, Computational Geometry: Theory and Applications, v.43 n.1, p.59-66, January, 2010
	Sariel Har-Peled , Dan Roth , Dav Zimak, Maximum margin coresets for active and noise tolerant learning, Proceedings of the 20th international joint conference on Artifical intelligence, p.836-841, January 06-12, 2007, Hyderabad, India