Dynamic well-spaced point sets (Q1947994)

The authors consider the dynamic well-spaced point set problem, which requires constructing a well-spaced superset of a dynamically changing input set, e.g., as input points are inserted or deleted. They present a dynamic algorithm that allows inserting/deleting points into/from the input in \(O(\log \Delta )\) time, where \(\Delta\) is the geometric spread, a natural measure that yields an \(O(\log n)\) bound when input points are represented by log-size words. It is shown that this algorithm is time-optimal by proving a lower bound of \(\Omega (\log \Delta )\) for a dynamic update. Also, they show that this algorithm maintains size-optimal outputs: the well-spaced supersets are within a constant factor of the minimum possible size. The asymptotic bounds in the paper's results work in any constant dimensional space. Experiments with a preliminary implementation indicate that dynamic changes may be performed with considerably greater efficiency than re-constructing a well-spaced point set from a scratch. These are the first time- and size-optimal algorithms for dynamically maintaining well-spaced point sets.