Clustering Motion

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