Interpolation par voisins naturels

L'interpolation par voisins naturels est une méthode d'interpolation multivariée, développée par Robin Sibson (en)[1]. La méthode est basée sur le diagramme de Voronoi d'un ensemble discret de points dans l'espace. Elle présente des avantages sur des méthodes plus simples d'interpolation, comme l'interpolation au plus proche voisin, en donnant une approximation plus lisse de la fonction interpolée.

Interpolation par voisins naturels avec poids de Sibson en 2D. La surface des disques verts correspondant au poids (wi). La région en violet correspond à la nouvelle cellule de Voronoi après avoir inséré un point d'interpolation (point noir). Les poids représentent l'intersection de la surface violette avec chacune des cellules voisines

L'estimation se calcule par :

avec G(x) l'approximation au point x, wi les poids et f(xi) les valeurs connues de la fonction de référence aux points (xi).

Poids de Sibson

La méthode de Sibson pour définir les poids wi consiste à calculer la part du volume de la cellule de Voronoi liée à x prise aux autres cellules. Pour la calculer, il faut considérer le diagramme de Voronoi de référence (lié aux points (xi)) et un second, lié aux points (xi) et au point x. Ainsi, une nouvelle cellule apparait, liée à x. Ainsi, en désignant par A(x) le volume de cette nouvelle cellule et A(xi) le volume de l’intersection entre la nouvelle cellule liée à x et l’ancienne cellule liée à xi, le poids est défini par :

Interpolation par voisins naturels avec poids de Laplace en 2D. L'interface l(xi) entre les cellules liées a x et xi est en bleu, et la distance d(xi) entre x et xi en rouge.
Poids de Laplace

On peut définir les poids par [2],[3]

l(xi) désigne la mesure de l'interface entre les cellules liées à x et xi dans le nouveau diagramme de Voronoi (longueur d'arête en 2D, surface en 3D) et d(xi), la distance entre x et (xi).

Voir aussi

modifier

Références

modifier
  1. (en) R. Sibson, Interpreting Multivariate Data, Chichester, John Wiley, , 21–36 p., « A brief description of natural neighbor interpolation (Chapter 2) »
  2. (en) N.H. Christ, R. Friedberg, R. et T.D. Lee, « Weights of links and plaquettes in a random lattice », Nuclear Physics B, vol. 210, no 3,‎ , p. 337-346
  3. (en) V.V. Belikov, V.D. Ivanov, V.K. Kontorovich, S.A. Korytnik et A.Y. Semenov, « The non-Sibsonian interpolation: A new method of interpolation of the values of a function on an arbitrary set of points », Computational mathematics and mathematical physics, vol. 37, no 1,‎ , p. 9-15