Smooth kinetic maintenance of clusters
John E. Hershberger · 2003
We propose a simple, deterministic kinetic data structure (KDS) for maintaining a covering of moving points by axis-aligned unit boxes in Rd. 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.