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³ \) Monte Carlo simulations on diagrams of \ (10⁴ \) 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.
Carlos M Hernandez-Suarez (Mon,) studied this question.