Smooth kinetic maintenance of clusters

摘要

We propose a simple, deterministic kinetic data structure (KDS) for maintaining a covering of moving points by axis-aligned unit boxes in R~d. The number of boxes is always within a factor of 3d of the best possible static covering. In the plane, this approximation factor (9) compares favorably with the approximation factor (around one million) of the best previous algorithm. The new KDS is efficient, local, compact, and responsive.