Algorithme de Preparata-Hong
En mathématiques et en informatique, plus particulièrement en géométrie algorithmique, l'algorithme de Preparata-Hong est une méthode algorithmique pour calculer le plus petit polygone (dans le plan) ou polyèdre (dans l'espace) qui englobe un ensemble fini de points donnés. Autrement dit, il s'agit de calculer l'enveloppe convexe d'un ensemble fini de points dans l'espace euclidien de dimension 2 (le plan) ou de dimension 3 (l’espace). Cette méthode a été mise au point par Franco Preparata et Su Ji Hong[1]. Sa stratégie repose sur le paradigme connu en informatique sous le nom de « diviser pour régner ». Cet article présente uniquement le cas de la dimension 2.
Description du problème
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/16/Envoltura_convexa_de_puntos.png/220px-Envoltura_convexa_de_puntos.png)
On considère un ensemble fini de points. On suppose que tous les points ont toutes leurs coordonnées différentes (si tel n'est pas le cas, on supprime les doublons et on adapte la procédure). On cherche à trouver les sommets du polygone convexe qui contient tous les points de .
Principe en dimension 2
modifierOn commence par trier les points de dans l'ordre croissant selon la dernière (c'est-à-dire la deuxième) coordonnée. Soit la liste des points de après ce tri.
Premiers cas
modifierLes premiers cas de l’algorithme diviser pour régner sont ceux où il y a 1, 2 ou 3 points dans . Dans ce cas, le calcul de l’enveloppe convexe est facile : il s'agit du point lui-même dans le premier cas, du segment joignant les 2 points dans le deuxième cas et du triangle de sommet les 3 points pour le troisième cas.
Cas général : procédure récursive
modifierS’il y a strictement plus de 3 points, on applique la stratégie diviser pour régner[1]. « Diviser » signifie ici qu'on sépare l’ensemble des points en deux parties, dites respectivement « inférieure » et « supérieure », avec le même nombre de points, à un point près au plus. On note et les deux sous-ensembles obtenus ; ils forment une partition de . À cause de la convention d'ordonnancement des points, les premiers points du tri ont les deuxièmes coordonnées les plus petites, et est donc la moitié (plus éventuellement un point) des points de dont les ordonnées sont les plus petites, c'est-à-dire qui sont le plus « bas » dans une représentation plane. De même, , le complémentaire de dans , comprend les points de dont les deuxièmes coordonnées, leurs ordonnées, sont les plus grandes, donc les points qui sont les plus « hauts » dans le plan.
L'étape « Régner » consiste alors à calculer les enveloppes convexes respectives de et . On appelle pour simplifier « enveloppe convexe inférieure » l'enveloppe convexe de et « enveloppe convexe supérieure » l'enveloppe convexe de . Cette étape se fait récursivement en divisant à nouveau les deux parties, et ainsi de suite.
Il faut donc aussi savoir reconstruire l’enveloppe convexe globale à partir des enveloppes convexes inférieure et supérieure : cela s'effectue grâce à un algorithme dit « algorithme de fusion », qui relie les deux enveloppes à la fois à gauche et à droite (ici, « à gauche » correspond aux premières coordonnées les plus petites, « à droite » aux plus grandes). À droite, par exemple, l'algorithme va permettre de relier deux points provenant respectivement des parties inférieure et supérieure, en faisant en sorte que tous les points de , dans les deux parties, soient tous à gauche de la droite joignant ces deux points.
-
Les enveloppes convexes supérieure et inférieure à fusionner.
-
Jointure des enveloppes convexes.
-
L'enveloppe convexe finale fusionnée.
Le principe de cet algorithme est le suivant[1] :
- On part des points les plus à droite de chaque partie, c'est-à-dire des points dont la première coordonnée, l'abscisse, est la plus grande ; on appelle le plus à droite dans et le plus à droite dans ,
- On cherche dans tel que la pente de la droite soit supérieure à la pente de la droite ,
- On cherche dans tel que la pente de la droite soit inférieure à la pente de la droite ,
- On itère jusqu’à rencontrer un blocage.
À la fin de cet algorithme, on relie les deux derniers points trouvés, dans et respectivement.
On réalise ensuite la même opération à gauche de et , c'est-à-dire en partant des points dont la première coordonnée est la plus petite et en adaptant l’algorithme ci-dessus. On retire enfin les arêtes joignant des points intérieurs au nouveau polygone et devenues donc superflues, pour obtenir l'enveloppe convexe globale de .
Algorithme de fusion dans le cas de la dimension 2
modifierDécrivons ici l'algorithme que l'on va utiliser pour fusionner les enveloppes convexes supérieure et inférieure[1]. Soient et deux polygones convexes du plan euclidien. Soient des entiers strictement positifs, représentant respectivement le nombre de sommets de et de . Soient et les sommets en question. On suppose que les ordonnées des points du premier ensemble sont toutes strictement inférieures à celles des points du second ensemble. On suppose que dans la réunion de ces deux ensembles, les abscisses et les ordonnées sont distinctes deux-à-deux. Supposons aussi que dans chaque ensemble, on range les sommets dans le sens horaire de leur parcours sur le polygone à partir du sommet le plus "à droite" (celui d'abscisse la plus grande, il est représenté sur les figures ci-contre respectivement pour A et B par et ). À l'aide de l'algorithme précédent, on cherche à calculer l'enveloppe convexe de la réunion de ces deux ensembles de points, qu'on va noter , à partir de et . Pour des raisons pratiques, on pourra raisonner sur les indices des sommets de et respectivement modulo et modulo . Nous allons considérer que (le cas se traite de manière analogue, en ce qui concerne à la fois le pseudo-code et la correction).
Pour et , on note la pente de la droite . Pour on note la pente de la droite et pour on note la pente de la droite . On note et respectivement les indices du sommet de le plus "à gauche" (celui d'abscisse la plus petite) et du sommet de le plus "à gauche" (celui d'abscisse la plus petite).
Le but de l'algorithme qui va suivre est de trouver la tangente droite de . Voici le pseudo-code de l'algorithme, on notera et respectivement l'abscisse et l'ordonnée de où est un point du plan euclidien, et on suppose que les coordonnées des sommets de et et que les valeurs pour et pour sont stockées dans des tableaux (accessibles à coût constant) :
Soient
On écrit
Si et faire et recommencer à partir de
Si et faire et recommencer à partir de
Renvoyer le couple
Il est facile de voir que l'algorithme termine car on incrémente et de 1 à chaque fois que l'on doit recommencer à partir de la ligne du pseudo-code ; dans le cas marginal où et , on passe directement à la dernière ligne de pseudo-code.
On remarque donc aussi que la complexité de l'algorithme est de l'ordre de , et donc de l'ordre de .
Correction de l'algorithme
modifierRechercher la tangente droite consiste à trouver les indices dans et dans telles que les points et soient ses extrémités. On se restreint au cas et .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/D%C3%A9croissance_des_pentes_alpha_%28i%2C_i%2B1%29.png/220px-D%C3%A9croissance_des_pentes_alpha_%28i%2C_i%2B1%29.png)
Grâce à la convexité de et , on remarque que les suites et sont décroissantes (la concaténation des segments associés est une fonction convexe).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/La_tangente_droite.png/220px-La_tangente_droite.png)
Ainsi, on peut caractériser géométriquement la pente de la tangente à droite pour qu'elle constitue bien un côté de l'enveloppe convexe issu de la fusion de et ) de la manière suivante :
- si , alors ;
- si , alors ;
- si , alors ;
- si , alors .
Il reste alors à montrer que l'algorithme renvoie bien ce que l'on souhaite, c'est-à-dire les indices dans et dans vérifiant la caractérisation ci-dessus.
On sait que l'algorithme s'arrête quand on a les deux conditions et . Pour être sûr que et , il faut s'assurer que l'on a l'intégralité de la caractérisation précédente. Pour cela, on distingue trois cas :
- soit on a , auquel cas on a directement la caractérisation, l'algorithme renvoie bien ce que l'on souhaite ;
- soit on a auquel cas soit une des deux dernières lignes du code n'est jamais exécutée, et on peut alors montrer facilement que l'on a la caractérisation voulue en examinant la seule ligne de code itérée ;
- soit il y a déjà eu une itération des deux dernières lignes de pseudo-code, et on distingue alors deux sous-cas :
l'indice est le dernier indice auquel on a fait une incrémentation, auquel cas on avait juste avant l'incrémentation, on a aussi (regarder le triangle sur la figure ci-contre) et par succession d'inégalités des pentes sur la chaîne , on réitère l'inégalité pour remonter à juste après la dernière incrémentation de l'indice (qui existe par hypothèse) et l'indice correspondant vérifie (car l'incrémentation de indique de et donc la chaîne est concave), par la chaîne d'inégalité on a bien , de même (par inégalité des pentes sur la fonction convexe issue de la chaîne ) cela donne : en incrémentant (de 1), on a finalement les conditions et ;
l'indice est le dernier indice auquel on a fait une incrémentation, juste avant cette incrémentation on a . De même on ne peut pas avoir , sinon on a la chaîne qui est concave, ce qui entraîne (inégalité des pentes) et comme la chaîne est concave par hypothèse, on obtient et donc que la chaine est concave , ce qui veut dire que ; si on revient sur le pseudo-code, si juste avant la dernière incrémentation de on avait une incrémentation de , alors on aurait eu d'après la troisième ligne de pseudo-code que , ce qui est impossible ; donc comme il est supposé qu'on a incrémenté au moins une fois, juste avant la dernière incrémentation de , on a encore une autre incrémentation de avec ; il s'obtient alors par récurrence qu'on ne va jamais atteindre dans l'exécution de l'algorithme : contradiction. On a alors la première inégalité . Aussi, comme la chaîne est concave par hypothèse, on obtient directement . Donc, en incrémentant (de 1), on a bien les conditions et .
Ceci termine la preuve de la correction de l'algorithme[1].
Complexité temporelle de l’algorithme
modifierOn suppose que pour un ensemble initial de points du plan, cet algorithme de fusion est exécuté en temps . Ainsi, en notant la complexité temporelle associée au calcul de l'enveloppe convexe de points du plan euclidien, stockés dans un tableau et triés par avance dans l'ordre croissant selon une coordonnée, on a la relation de récurrence suivante :
Par le master theorem[2],[3] ou par une analyse à la main, on conclut que est en . Comme le tri d'un tableau (par exemple par tri fusion) peut être réalisé en temps , la complexité totale de l'algorithme est elle aussi en .
Une autre approche du problème
modifierIl existe une autre façon de calculer l'enveloppe convexe de en calculant deux convexes non bornés tels que l'intersection des deux donne l'enveloppe convexe finale, et en déterminant pour chacun de ces convexes l'ensemble des segments et demi-droites qui les délimitent. Il s'agit d'une méthode proposée par F. Preparata et M. Shamos[4].
Notes et références
modifier- (en) Franco P. Preparata et Su Ji Hong, « Convex Hulls of Finite Sets of Points in Two and Three Dimensions », Communications of the ACM, vol. 20, no 2, , p. 87-93 (lire en ligne).
- (en) Sanjoy Dasgupta, Christos H. Papadimitriou et Umesh V. Vazirani, Algorithms, McGraw-Hill, .
- (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to algorithms, MIT Press, .
- (en) Franco P. Preparata et Michael Ian Shamos, Computational geometry, New York, Springer, (lire en ligne).
Voir aussi
modifierArticles connexes
modifierLiens externes
modifier- Danièle Beauquier, Jean Berstel et Philippe Chrétienne, « Éléments d'algorithmique », (consulté le ).