Streaming with minimum space: An algorithm for covering by two congruent balls

In this paper we design a simple streaming algorithm for maintaining two smallest balls (of equal radius) in d-dimension to cover a set of points in an on-line fashion. Different from most of the traditional streaming models, at any step we use the minimum amount of space by only storing the locations and the (common) radius of the balls. Previously, such a geometric algorithm is only investigated for covering with one ball (one-center) by Zarrabi-Zadeh and Chan (2006) [16]. We give an analysis of our algorithm, which is significantly different from the one-center algorithm due to the obvious possibility of grouping points wrongly under this streaming model. We show that our algorithm has an approximation ratio 2 for d=1 and at most 5.611 for any fixed d>1. We also present lower bounds of 1.5 and 1.604 for the problem in the d=1 and d>1 cases respectively.