Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

Timothy M. Chan; Vinayak Pathak

doi:10.1007/978-3-642-22300-6_17

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

At SODA'10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + √3)/2 + ε ≈ 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + √2)/2 ≈ 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
Pages	195-206
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-22300-6_17
State	Published - 2011
Externally published	Yes
Event	12th International Symposium on Algorithms and Data Structures, WADS 2011 - New York, NY, United States Duration: Aug 15 2011 → Aug 17 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6844 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Symposium on Algorithms and Data Structures, WADS 2011
Country/Territory	United States
City	New York, NY
Period	8/15/11 → 8/17/11

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-642-22300-6_17

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., & Pathak, V. (2011). Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings (pp. 195-206). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6844 LNCS). https://doi.org/10.1007/978-3-642-22300-6_17

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. / Chan, Timothy M.; Pathak, Vinayak.
Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. 2011. p. 195-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6844 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM & Pathak, V 2011, Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. in Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6844 LNCS, pp. 195-206, 12th International Symposium on Algorithms and Data Structures, WADS 2011, New York, NY, United States, 8/15/11. https://doi.org/10.1007/978-3-642-22300-6_17

Chan TM, Pathak V. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. 2011. p. 195-206. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22300-6_17

@inproceedings{96193861909c4be29120be1071a4e250,

title = "Streaming and dynamic algorithms for minimum enclosing balls in high dimensions",

abstract = "At SODA'10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + √3)/2 + ε ≈ 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + √2)/2 ≈ 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion.",

author = "Chan, {Timothy M.} and Vinayak Pathak",

year = "2011",

doi = "10.1007/978-3-642-22300-6_17",

language = "English (US)",

isbn = "9783642222993",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "195--206",

booktitle = "Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings",

note = "12th International Symposium on Algorithms and Data Structures, WADS 2011 ; Conference date: 15-08-2011 Through 17-08-2011",

}

TY - GEN

T1 - Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

AU - Chan, Timothy M.

AU - Pathak, Vinayak

PY - 2011

Y1 - 2011

N2 - At SODA'10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + √3)/2 + ε ≈ 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + √2)/2 ≈ 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion.

AB - At SODA'10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + √3)/2 + ε ≈ 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + √2)/2 ≈ 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion.

UR - http://www.scopus.com/inward/record.url?scp=80052118924&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052118924&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22300-6_17

DO - 10.1007/978-3-642-22300-6_17

M3 - Conference contribution

AN - SCOPUS:80052118924

SN - 9783642222993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 195

EP - 206

BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings

T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011

Y2 - 15 August 2011 through 17 August 2011

ER -

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this