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.3661.
We prove that the same algorithm has
approximation factor less than 1.22, which brings us
much closer to a 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(dlog n) expected amortized time
per insertion/deletion.
Finally, we prove that a 1+ϵ approximation to the problem can be found in (0.5+δ)/ϵ passes over the input, for an arbitrarily small constant δ, which is an improvement over the previous result that used 2/ϵ passes.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/6172 |
| Date | 23 August 2011 |
| Creators | Pathak, Vinayak |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0022 seconds