Home Bookmarks Papers Blog

Clustering Motion

Sariel Har-Peled

Given a set of moving points in Rd, we show that one can cluster them in advance, using a small number of clusters, so that in any point in time this static clustering is competitive with the optimal k-center clustering of the point-set at any point in time. The advantage of this approach is that it avoids the usage of kinetic data-structures and as such it does not need to update the clustering as time passes.

To implement this static clustering efficiently, we describe a simple technique for speeding-up clustering algorithms, and apply it to achieve a faster clustering algorithms for several problems. In particular, we present a linear time algorithm for computing a 2-approximation to the k-center clustering of a set of n points in Rd. This slightly improves over the algorithm of Feder and Greene [fg-oafac-88], that runs in \Theta(n log k) time(which is optimal in the comparison model).

Open office presentation: Presentation

FOCS presentation: HTML.
@string{DCG    = "Discrete Comput. Geom."}

   title       = "Clustering Motion",
   author      = "S. {Har-Peled}",
   journal     = DCG,
   volume      = 31,
   number      = 4,
   pages       = {545--565},
   year        = {2004}

Last modified: Fri Apr 4 17:00:04 CDT 2014