Fast and Accurate Reconstruction of Voronoi Generators in Large Tessellations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915357367730176 |
|---|---|
| author | Hernandez-Suarez, Carlos M |
| author_facet | Hernandez-Suarez, Carlos M |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19076 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast and Accurate Reconstruction of Voronoi Generators in Large Tessellations Hernandez-Suarez, Carlos M Metric Geometry 52C99, 68U05, 65D18 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. |
| title | Fast and Accurate Reconstruction of Voronoi Generators in Large Tessellations |
| topic | Metric Geometry 52C99, 68U05, 65D18 |
| url | https://arxiv.org/abs/2506.19076 |