Repair Entropy in Dynamic Geometric Nearest-Neighbour Structures

Abstract

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_2^i-d_1^i$. A triangle-inequality argument gives a sharp validity radius: after a step of maximum displacement $\epsilon$, every certificate with $c_i>4\epsilon$ remains valid, so all possible failures are confined to a repair frontier $F_t$. We introduce repair-frontier entropy $H(F_t)$, the normalized Shannon entropy of failed certificates over index cells, as a workload descriptor for choosing between event-driven repair, batched repair, and full rebuild. The resulting maintenance rule repairs only the frontier in $O(|F_t|\log N)$ time under bounded cell occupancy, while a full rebuild costs $\hat{I}˜(N)$; moreover, entropy lower-bounds the number of frontier cells touched by event-driven repair and shifts the empirical repair-rebuild crossover. We evaluate ten motion families in $d\in 2,3$, with $N$ up to $16,000$, using an exact tiled GPU oracle and a GPU grid rebuild as ground truth and competitor. Across $2400$ labelled transitions, the validity rule misses no invalid certificate, low-pressure frontiers are usually cheaper to repair incrementally, and diffuse frontiers of the same size are more expensive for event-driven repair but not for batched repair. The released dataset records frontier geometry, certificate audits, per-strategy times, and best-strategy labels.

10 pages, 2 figures, 2 tables; code and dataset provided as ancillary files