Algorithme de Shamos et Hoey
L'algorithme de Shamos et Hoey est un algorithme de construction du diagramme de Voronoï d'un ensemble de points. C'est un algorithme de type diviser pour régner.
Fusion de deux sous-diagrammes par l'algorithme de Shamos.
|
Principe et description
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 = cte 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 [GinfDinf] et [GsupDsup], où {Ginf, Gsup} ∈ G et {Dinf, Dsup} ∈ 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 [GinfDinf] ; 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 G1, et dans la cellule d'un point D1 de D, on est donc proche de G1 et de D1. La ligne brisée P continue donc selon la médiatrice de [G1D1], 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 [GsupDsup].
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 [GinfDinf]. Lorsque l'on « entre » dans une cellule, on s'éloigne du point ayant servi à créer à cette cellule.
Complexité
La complexité en temps de l'algorithme est O(n log n)[1].
Histoire
L'algorithme est dû a Shamos et Hoey en 1975[2].
Autres algorithmes
D'autres algorithmes pour le problème sont l'algorithme de Fortune et l'algorithme de Green et Sibson.
Notes et références
- Cet article est partiellement ou en totalité issu de l'article intitulé « Diagramme de Voronoï » (voir la liste des auteurs).
- Franck Hétroy, « Un peu de géométrie algorithmique, 4.2 Voronoı̈ : construction incrémentale », sur ENSIMAG.
- (en) Michael Ian Shamos, Computational Geometry : thèse de doctorat, université Yale,
(en) Michael Ian Shamos et Dan Hoey, « Closest-point problems », dans Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press, (lire en ligne), p. 151-162
Portail de l'informatique théorique 
Portail de la géométrie