Algorithme de Green et Sibson
# Algorithme de Green et Sibson

L'algorithme de Green et Sibson est un algorithme pour construire le diagramme de Voronoï d'un ensemble de points. C'est une méthode incrémentale qui maintient un diagramme de Voronoï, en ajoutant les points les uns après les autres.

## Principe

L'algorithme est incrémental. On ajoute les points les uns après les autres, en mettant à jour le diagramme. l'idée est que l'ajout d'un point ne va modifier le diagramme que localement.

## Description

Soit S = ${p_1,$ $p_2,$ …, $p_n}.$ Supposons que le diagramme est construit pour les k premiers germes ; on ajoute le germe k + 1. Comme le diagramme de Voronoï est une partition du plan, le point $p_{k+1}$ est nécessairement dans (au moins) une région du diagramme de Voronoï des k premiers points ; soit q le germe de cette région.

On considère la médiatrice de $[p_{k+1}q].$ Comme la région est convexe, cette médiatrice a exactement deux points d'intersection avec les parois de la cellule. Soient $x_1$ et $x_2$ ces points d'intersection, le triangle $qx_1x_2$ étant orienté dans le sens direct. Le segment $[x_1x_2]$ réduit la région Vor$_{{p1,…,pk}}$(q), ce qui nous donne directement Vor$_{{p1,…,pk+1}}$(q).

Le point $x_2$ est sur la paroi d'une cellule, il appartient donc également à une cellule générée par un germe r. On considère alors la médiatrice de $[p_{k+1}r],$ et ainsi de suite jusqu'à revenir au point $x_1.$ On trace ainsi une suite de parois qui font le tour du point $p_{k+1},$ et qui définissent de nouvelles cellules.

## Complexité

L'algorithme de Green et Sibson est de complexité en temps $O(n^2).$

## Histoire

Cet algorithme a été décrit par Peter Green et Robin Sibson en 1978.

## Autres algorithmes

D'autres algorithmes sont plus rapides, de complexité $O(n\log n)$, comme l'algorithme de Fortune et l'algorithme de Shamos et Hoey. Le premier est un algorithme de type sweep line et le second est de type diviser pour régner.

