Repair Entropy in Dynamic Geometric Nearest-Neighbour Structures (opens in new tab)

We study dynamic geometric data structures for exact nearest-neighbour maintenance under small motions. For each point we store a certificate consisting of its nearest neighbour and the two smallest neighbour distances, with clearance $c_i=d^i_2-d^i_1$. A triangle-inequality argument gives a sharp validity radius: after a step of maximum displacement $\varepsilon$, every certificate with $c_i>4\varepsilon$ remains valid, so all possible failures...