Algorithme de Shamos et Hoey

L'algorithme est basé sur un raisonnement par récurrence : supposons que l'on puisse séparer l'ensemble S en deux sous-ensembles de même cardinal n/2, séparés par une droite verticale : l'ensemble G des points à gauche et l'ensemble D des points à droite. Les diagrammes respectifs de ces sous-ensembles, V(G) et V(D), sont connus, et on peut les fusionner[1].

On a ainsi un algorithme de type diviser pour régner, dont la complexité est O(n log n).

Il faut ensuite déterminer la complexité de la fusion des sous-diagrammes.

Il existe une ligne polygonale P telle que :

• les points à gauche de cette ligne sont plus proches des points de G que de n'importe quel point de D ;
• les points à droite de cette ligne sont plus proches des points de D que de n'importe quel point de G.

Cette ligne est celle qui séparera les cellules de V(G) et les cellules de V(D) qui se recouvrent. Cette ligne est monotone en y (l'intersection d'une droite horizontale y = c^te avec P est un point unique), on peut donc construire cette ligne par un balayage simple des diagrammes V(G) et V(D).

On commence par raccorder les enveloppes convexes et G et de D ; cela nécessite la création de deux segments de droite [G_infD_inf] et [G_supD_sup], où {G_inf, G_sup} ∈ G et {D_inf, D_sup} ∈ D (ce sont des points des enveloppes convexes). Le premier élément de la ligne brisée est une demi-droite inférieure de la médiatrice de [G_infD_inf] ; cette demi-droite s'arrête sur le premier segment de V(G) ou V(D) rencontré (dans la figure ci-contre, il s'agit de l'intersection d'un segment de chaque diagramme).

Si l'on continue tout droit, on pénètre dans la cellule d'un point de G, appelons-le G₁, et dans la cellule d'un point D₁ de D, on est donc proche de G₁ et de D₁. La ligne brisée P continue donc selon la médiatrice de [G₁D₁], et elle s'étend jusqu'à rencontrer un segment de V(G) ou de V(D). Et ainsi de suite, la ligne P suit des médiatrices de segments formés d'un point de G et d'un point de D. Elle se termine par une demi-droite portée par la médiatrice de [G_supD_sup].

Cette ligne P tronque les diagrammes V(G) et V(D), et est leur ligne de raccordement.

Aux étapes élémentaires, on n'a que deux points, et les diagrammes sont évidemment délimités par la médiatrice.

La construction des enveloppes convexes est en O(n log n) ou O(n log m), m étant le nombre de points de l'enveloppe (m ≤ n). Le raccordement des enveloppes convexes et la construction de P sont en O(n). On a donc une complexité globale en O(n log n).

La construction du diagramme des points les plus éloignés se fait de a même manière, en partant de la partie supérieure de la médiatrice de [G_infD_inf]. Lorsque l'on « entre » dans une cellule, on s'éloigne du point ayant servi à créer à cette cellule.

La complexité en temps de l'algorithme est O(n log n)[1].

L'algorithme est dû a Shamos et Hoey en 1975[2].

D'autres algorithmes pour le problème sont l'algorithme de Fortune et l'algorithme de Green et Sibson.

• Cet article est partiellement ou en totalité issu de l'article intitulé « Diagramme de Voronoï » (voir la liste des auteurs).