Sibson's formula for higher order Voronoi diagrams
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913331027116032 |
|---|---|
| author | Claverol, Mercè Heras-Parrilla, Andrea de las Huemer, Clemens Lara, Dolores |
| author_facet | Claverol, Mercè Heras-Parrilla, Andrea de las Huemer, Clemens Lara, Dolores |
| contents | Let $S$ be a set of $n$ points in general position in $\mathbb{R}^d$. The order-$k$ Voronoi diagram of $S$, $V_k(S)$, is a subdivision of $\mathbb{R}^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_2(S)$ and the cell of $Q$ in $V_1(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17422 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sibson's formula for higher order Voronoi diagrams Claverol, Mercè Heras-Parrilla, Andrea de las Huemer, Clemens Lara, Dolores Computational Geometry Let $S$ be a set of $n$ points in general position in $\mathbb{R}^d$. The order-$k$ Voronoi diagram of $S$, $V_k(S)$, is a subdivision of $\mathbb{R}^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_2(S)$ and the cell of $Q$ in $V_1(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. |
| title | Sibson's formula for higher order Voronoi diagrams |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2404.17422 |