Clustering Motion

Sariel Har-Peled

Given a set of moving points in R^d, 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 R^d. 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).

Abstract - Postscript, PDF.
Presentation

FOCS presentation: HTML.

@string{DCG    = "Discrete Comput. Geom."}

@article{h-cm-04,
   title       = "Clustering Motion",
   author      = "S. {Har-Peled}",
   journal     = DCG,
   volume      = 31,
   number      = 4,
   pages       = {545--565},
   year        = {2004},
   url         = {http://www.uiuc.edu/~sariel/research/papers/01/cluster/}
}

Last modified: Fri Jul 7 18:10:40 EDT 2000