Clustering motion

Research output: Contribution to journalArticlepeer-review


Given a set of moving points in ℝd, we show how to cluster them in advance, using a small number of clusters, so that at any time this static clustering is competitive with the optimal k-center clustering at that time. The advantage of this approach is that it avoids updating the clustering as time passes. We also show how to maintain this static clustering efficiently under insertions and deletions. To implement this static clustering efficiently, we describe a simple technique for speeding up clustering algorithms and apply it to achieve 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 ℝd. This slightly improves the algorithm of Feder and Greene, that runs in Θ(n log k) time (which is optimal in the algebraic decision tree model).

Original languageEnglish (US)
Pages (from-to)545-565
Number of pages21
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Jun 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Clustering motion'. Together they form a unique fingerprint.

Cite this