New Computational Geometry Paper Introduces Repair Entropy for Dynamic Nearest-Neighbour Structures

Researchers have submitted a new paper to the Computer Science > Computational Geometry category on arXiv introducing a novel approach to maintaining dynamic geometric data structures. The work, titled "Repair Entropy in Dynamic Geometric Nearest-Neighbour Structures," addresses the challenge of efficiently updating nearest-neighbour information when points undergo small motions.

The research centres on a certificate-based approach where each point stores its nearest neighbour and the two smallest neighbour distances. A key theoretical contribution is a sharp validity radius derived from triangle-inequality arguments: certificates with clearance greater than 4ε remain valid after a displacement step of maximum size ε. This allows researchers to identify a "repair frontier" containing only the failed certificates that require updating.

The authors introduce repair-frontier entropy as a metric to describe the workload and guide decisions between three maintenance strategies: event-driven repair, batched repair, and full rebuild. Their approach achieves O(|F_t| log N) time complexity for frontier-only repairs under bounded cell occupancy, compared to Θ(N) for a complete rebuild. Testing across ten motion families with up to 16,000 points in two and three dimensions, the researchers evaluated 2,400 labelled state transitions using a GPU oracle and grid rebuild as ground truth. Results show that the validity rule successfully identified all invalid certificates, low-pressure frontiers were typically cheaper to repair incrementally, and diffuse frontiers exhibited different performance profiles for event-driven versus batched repair strategies.

The paper releases a comprehensive dataset including frontier geometry, certificate audits, per-strategy execution times, and optimal strategy labels for each transition. Supporting materials include source code modules for certificate management, indexing, metrics computation, and GPU-based oracle implementations, along with detailed trace data and figures documenting the phase diagram and matched repair scenarios.