Clustering Motion |
| |
Authors: | Email author" target="_blank">Sariel?Har-PeledEmail author |
| |
Institution: | (1) Department of Computer Science, DCL 2111, University of Illinois, 1304 West Springfield Avenue, Urbana, IL 61801, USA |
| |
Abstract: | 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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|