Clustering motion

Research output: Contribution to journalConference articlepeer-review

Abstract

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 this 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, that runs in Θ (n log k) time (which is optimal in the comparison model).

Original languageEnglish (US)
Pages (from-to)84-93
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
DOIs
StatePublished - 2001
Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
Duration: Oct 14 2001Oct 17 2001

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

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

Cite this