Fast and Accurate Reconstruction of Voronoi Generators in Large Tessellations

A Voronoi diagram partitions the plane into convex cells, each containing the points closest to a single generator. Given such a tessellation, the inverse Voronoi problem seeks the generator set $S$ that produced it. Our algorithm selects a single interior cell with $k$ edges and solves a compact, consistent linear system with $2(k+1)$ unknowns and $4k$ scalar equations to recover that cell’s generator together with the $k$ generators of its neighbors in one step. The remaining sites follow by successive geometric reflections. The overall running time is $O(n)$ for a diagram with $n$ cells. Across ${10}^3$ Monte Carlo simulations on diagrams of ${10}^4$ cells, the method achieved an average RMSE of ${10}^{-12}$ and a worst-case individual reconstruction error of ${10}^{-8}$, demonstrating both efficiency and robustness.