Smooth kinetic maintenance of clusters (Q1775777)

The author identifies two significant deficiencies in the solution of the clustering problem as presented by \textit{Gao} et al. [Proc. 17th Annual ACM Symposium Comput. Geom., 188--196 (2001)]. It is further observed that the efficiency, responsiveness, etc. of the kinetic data structure (KDS) are not guaranteed, but hold only with a high probability. The author proposes here a simple, deterministic KDS that maintains a covering of moving points by unit boxes in \({\mathbb R}^d\). It is claimed that this KDS is efficient, local, compact, and responsive with somewhat better bounds than the previous algorithm for all of these measures.