Given a convex polygon @math with @math vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover @math . We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius @math satisfying @math using @math space, where @math is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by @math , maintaining the time complexity of the algorithm to @math , and using @math extra space in addition to the space required for storing the input.
At [email protected]?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) [email protected] 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(dlogn) expected amortized time per insertion deletion. We develop (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in Rd. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sublinear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n. Abstract In the k -center problem for streaming points in d -dimensional metric space, input points are given in a data stream and the goal is to find the k smallest congruent balls whose union covers all input points by examining them. In the single-pass streaming model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. In this paper, we present a single-pass, ( 1.8 + e ) -factor, O ( d e ) -space data stream algorithm for the Euclidean 2-center problem for any d ≥ 1 . This is the first result with an approximation factor below 2 using O ( d e ) space for any d . Our algorithm naturally extends to the Euclidean k -center problem with k > 2 . We present a single-pass ( 1.8 + e ) -factor data stream algorithm for the Euclidean k -center problem for any d ≥ 1 , which uses O ( 2 k ( k + 3 ) ! d e ) space and O ( 2 k ( k + 2 ) ! d e ) update time. In this paper we investigate algorithms and lower bounds for summarization problems over a single pass data stream. In particular we focus on histogram construction and K-center clustering. We provide a simple framework that improves upon all previous algorithms on these problems in either the space bound, the approximation factor or the running time. The framework uses a notion of "streamstrapping" where summaries created for the initial prefixes of the data are used to develop better approximation algorithms. We also prove the first non-trivial lower bounds for these problems. We show that the stricter requirement that if an algorithm accurately approximates the error of every bucket or every cluster produced by it, then these upper bounds are almost the best possible. This property of accurate estimation is true of all known upper bounds on these problems. Abstract Given a set P of n points in the plane, we seek two squares such that their center points belong to P , their union contains P , and the area of the larger square is minimal. We present efficient algorithms for three variants of this problem: in the first the squares are axis parallel, in the second they are free to rotate but must remain parallel to each other, and in the third they are free to rotate independently.