Sibson's formula for higher order Voronoi diagrams

2024/04/26 by Mercè Claverol Aguas, Claverol, Mercè, Andrea de las Heras-Parrilla +5
Physics and Astronomy · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Force Microscopy Techniques and Applications

paper · pdf · doi:10.48550/arxiv.2404.17422

openalex publication_date 2024/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let S be a set of n points in general position in ℝ^d. The order-k Voronoi diagram of S, V_k(S), is a subdivision of ℝ^d into cells whose points have the same k nearest points of S. Sibson, in his seminal paper from 1980 (A vector identity for the Dirichlet tessellation), gives a formula to express a point Q of S as a convex combination of other points of S by using ratios of volumes of the intersection of cells of V₂(S) and the cell of Q in V₁(S). The natural neighbour interpolation method is based on Sibson's formula. We generalize his result to express Q as a convex combination of other points of S by using ratios of volumes from Voronoi diagrams of any given order.

Related

• The edge labeling of higher order Voronoi diagrams
• On the Structure of Higher Order Voronoi Cells
• Construction of the Voronoi Diagram and Secondary Polytope
• Sublinear Explicit Incremental Planar Voronoi Diagrams
• Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon