Algorithme de Preparata-Hong

On considère un ensemble fini ${\displaystyle P}$ de points. On suppose sans perte de généralité que tous les points ont toutes leurs coordonnées différentes. On cherche à trouver les sommets de son polygone convexe.

On commence par ranger les points de ${\displaystyle P}$ dans l'ordre croissant selon la dernière (i.e. deuxième) coordonnée. Notons ${\displaystyle n}$ le cardinal de ${\displaystyle P}$. Soit ${\displaystyle \{x_{1},...,x_{n}\}}$ l'ensemble ${\displaystyle P}$ après le tri.

Détermination de la tangente à droite

     

 

C'est l'algorithme que l'on va utiliser pour fusionner les enveloppes convexes supérieur et inférieur.

Soient ${\displaystyle A}$ et ${\displaystyle B}$ deux polygones convexes du plan euclidien.

Soient ${\displaystyle n,m}$ des entiers strictement positifs, représentant respectivement le nombre de sommets de ${\displaystyle A}$ et de ${\displaystyle B}$. Soient ${\displaystyle \{a_{1},...,a_{n}\}}$ et ${\displaystyle \{b_{1},...,b_{m}\}}$ 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 ${\displaystyle r_{A}}$ et ${\displaystyle r_{B}}$). À 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 ${\displaystyle C}$, à partir de ${\displaystyle A}$ et ${\displaystyle B}$. Pour des raisons pratiques, on pourra raisonner sur les indices des sommets de ${\displaystyle A}$ et ${\displaystyle B}$ respectivement modulo ${\displaystyle n}$ et modulo ${\displaystyle m}$. Nous allons considérer que ${\displaystyle x_{1}(a_{1})<x_{1}(b_{1})}$ (le cas ${\displaystyle x_{1}(a_{1})>x_{1}(b_{1})}$ se traite de manière analogue, en ce qui concerne à la fois le pseudo-code et la correction).

Pour ${\displaystyle i=1,...,n}$ et ${\displaystyle j=1,...,m}$, on note ${\displaystyle p_{i,j}}$ la pente de la droite ${\displaystyle (a_{i},b_{j})}$. Pour ${\displaystyle i=1,...,n}$ on note ${\displaystyle \alpha _{i,i+1}}$ la pente de la droite ${\displaystyle (a_{i},a_{i+1})}$ et pour ${\displaystyle j=1,...,m}$ on note ${\displaystyle \beta _{j,j+1}}$ la pente de la droite ${\displaystyle (b_{j},b_{j+1})}$. On note ${\displaystyle g_{A}}$ et ${\displaystyle g_{B}}$ respectivement les indices du sommet de ${\displaystyle A}$ le plus "à gauche" (celui d'abscisse la plus petite) et du sommet de ${\displaystyle B}$ le plus "à gauche" (celui d'abscisse la plus petite).

Le but de l'algorithme qui va suivre est de trouver la tangente droite de ${\displaystyle C}$. Voici le pseudo-code de l'algorithme, on notera ${\displaystyle x_{1}(c)}$ et ${\displaystyle x_{2}(c)}$ respectivement l'abscisse et l'ordonnée de ${\displaystyle c}$ où ${\displaystyle c}$ est un point du plan euclidien, et on suppose que les coordonnées des sommets de ${\displaystyle A}$ et ${\displaystyle B}$ et que les valeurs ${\displaystyle \alpha _{i,i+1}}$ pour ${\displaystyle i=1,...,n}$ et ${\displaystyle \beta _{j,j+1}}$ pour ${\displaystyle j=1,...,m}$ sont stockées dans des tableaux (accessibles à coût constant) :

Soient ${\displaystyle i\leftarrow 1,j\leftarrow 1}$

${\displaystyle (***)}$ On écrit ${\displaystyle p_{i,j}={\frac {x_{2}(bj)-x_{2}(ai)}{x_{1}(bj)-x_{1}(ai)}}}$

Si ${\displaystyle \alpha _{i,i+1}\geq p_{i,j}}$ et ${\displaystyle i<g_{A}}$ faire ${\displaystyle i\leftarrow i+1}$ et recommencer à partir de ${\displaystyle (***)}$

Si ${\displaystyle \beta _{j,j+1}>p_{i,j}}$ et ${\displaystyle j<g_{B}}$ faire ${\displaystyle j\leftarrow j+1}$ et recommencer à partir de ${\displaystyle (***)}$

Renvoyer le couple ${\displaystyle (i,j)}$

Il est facile de voir que l'algorithme termine car on incrémente ${\displaystyle i}$ et ${\displaystyle j}$ de 1 si on doit recommencer à partir de la deuxième ligne de pseudo-code et dans le cas marginal où ${\displaystyle i=g_{A}}$ et ${\displaystyle j=g_{B}}$ on passe directement à la dernière ligne de pseudo-code. De là, on remarque aussi que la complexité de l'algorithme est en ${\displaystyle O(g_{A}+g_{B})}$, et donc en ${\displaystyle O(n+m)}$.

Rechercher la tangente droite consiste à trouver les indices ${\displaystyle i^{*}}$ dans ${\displaystyle \{1,...,g_{A}\}}$ et ${\displaystyle j^{*}}$ dans ${\displaystyle \{1,...,g_{B}\}}$ telles que les points ${\displaystyle a_{i^{*}}}$ et ${\displaystyle b_{j^{*}}}$ soient ses extrémités. On se restreint au cas ${\displaystyle i^{*}\neq g_{A}}$ et ${\displaystyle j^{*}\neq g_{B}}$.

Notons déjà quelques résultats qui s'obtiennent grâce à la convexité de ${\displaystyle A}$ et ${\displaystyle B}$ :

ligne brisée convexe

• la suite ${\displaystyle (\alpha _{1,2},...,\alpha _{g_{A}-1,g_{A}})}$ est décroissante (voir la concaténation des segments associés comme une fonction convexe)

• la suite ${\displaystyle (\beta _{1,2},...,\beta _{g_{B}-1,g_{B}})}$ est décroissante (voir également la concaténation des segments associés comme une fonction convexe)

tangente droite pour les convexes A et B

Ainsi, on peut caractériser géométriquement la pente de la tangente droite (de façon à ce qu'elle constitue bien un côté de l'enveloppe convexe issu de la fusion de ${\displaystyle A}$ et ${\displaystyle B}$) par :

• si ${\displaystyle i^{*}>1}$, alors ${\displaystyle \alpha _{i^{*},i^{*}+1}<p_{i^{*},j^{*}}\leq \alpha _{i^{*}-1,i^{*}}}$ ;

• si ${\displaystyle i^{*}=1}$, alors ${\displaystyle \alpha _{1,2}<p_{1,j^{*}}}$ ;

• si ${\displaystyle j^{*}>1}$, alors ${\displaystyle \beta _{j^{*},j^{*}+1}\leq p_{i^{*},j^{*}}<\beta _{j^{*}-1,j^{*}}}$ ;

• si ${\displaystyle j^{*}=1}$, alors ${\displaystyle \beta _{1,2}\leq p_{i*,1}}$.

Il reste alors à montrer que l'algorithme renvoie bien ce que l'on souhaite, c'est-à-dire les indices ${\displaystyle i^{*}}$ dans ${\displaystyle \{1,...,g_{A}\}}$ et ${\displaystyle j^{*}}$ dans ${\displaystyle \{1,...,g_{B}\}}$ vérifiant la caractérisation ci-dessus.

On sait que l'algorithme s'arrête quand on a les deux conditions ${\displaystyle \alpha _{i^{*},i^{*}+1}<p_{i^{*},j^{*}}}$ et ${\displaystyle \beta _{j^{*},j^{*}+1}\leq p_{i^{*},j^{*}}}$. Pour être sûr que ${\displaystyle i=i^{*}}$ et ${\displaystyle j=j^{*}}$, 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 ${\displaystyle i=j=1}$, auquel cas on a directement la caractérisation, l'algorithme renvoie bien ce que l'on souhaite ;

• soit on a ${\displaystyle (i=1\ et\ j>1)\ ou\ (i>1\ et\ j=1)}$ auquel cas soit la ligne 3 soit la ligne 4 n'est jamais exécutée, on peut alors montrer facilement que l'on a caractérisation en se penchant sur la seule ligne itérée ;

• soit il y a déjà eu une itération de la ligne 3 et la ligne 4 de pseudo-code, on distingue alors deux sous-cas :

${\displaystyle (1)}$ l'indice ${\displaystyle j}$ est le dernier indice auquel on a fait une incrémentation, auquel cas on avait ${\displaystyle \beta _{j,j+1}>p_{i,j}>\alpha _{i,i+1}}$ juste avant l'incrémentation, on a aussi ${\displaystyle p_{i,j+1}\leq p_{i,j}}$ (regarder le triangle ${\displaystyle (a_{i},b_{j},b_{j+1})}$ sur la figure ci-contre) et par succession d'inégalités des pentes sur la chaîne ${\displaystyle (a_{i},b_{j+1},b_{j},...,b_{1})}$, on réitère l'inégalité pour remonter à juste après la dernière incrémentation de l'indice ${\displaystyle i}$ (qui existe par hypothèse) et l'indice ${\displaystyle j_{0}}$ correspondant vérifie ${\displaystyle p_{i,j_{0}}\leq \alpha _{i-1,i}}$ (car l'incrémentation de ${\displaystyle i}$ indique de ${\displaystyle p_{i-1,j_{0}}\leq \alpha _{i-1,i}}$ et donc la chaîne ${\displaystyle (a_{i},a_{i-1},b_{j_{0}})}$ est concave), par la chaîne d'inégalité on a bien ${\displaystyle p_{i,j}\leq \alpha _{i-1,i}}$, de même (par inégalité des pentes sur la fonction convexe issue de la chaîne ${\displaystyle (a_{i},b_{j+1},b_{j})}$) cela donne ${\displaystyle \beta _{j,j+1}>p_{i,j+1}}$ : en incrémentant ${\displaystyle j}$ (de 1), on a finalement les conditions ${\displaystyle p_{i,j}\leq \alpha _{i,i-1}}$ et ${\displaystyle p_{i,j}<\beta _{j-1,j}}$ ;

${\displaystyle (2)}$ l'indice ${\displaystyle i}$ est le dernier indice auquel on a fait une incrémentation, juste avant cette incrémentation on a ${\displaystyle \alpha _{i,i+1}\geq p_{i,j}}$. De même on ne peut pas avoir ${\displaystyle \beta _{j-1,j}\leq p_{i+1,j}}$, sinon on a la chaîne ${\displaystyle (a_{i+1},b_{j},b_{j-1})}$ qui est concave, ce qui entraîne (inégalité des pentes) ${\displaystyle p_{i+1,j}\geq p_{i+1,j-1}}$ et comme la chaîne ${\displaystyle (a_{i+1},a_{i},b_{j})}$ est concave par hypothèse, on obtient ${\displaystyle \alpha _{i,i+1}\geq p_{i+1,j-1}}$ et donc que la chaine ${\displaystyle (a_{i+1},a_{i},b_{j-1})}$ est concave , ce qui veut dire que ${\displaystyle \alpha _{i,i+1}\geq p_{i,j-1}}$ ; si on revient sur le pseudo-code, si juste avant la dernière incrémentation de ${\displaystyle i}$ on avait une incrémentation de ${\displaystyle j}$, alors on aurait eu d'après la troisième ligne de pseudo-code que ${\displaystyle \alpha _{i,i+1}<p_{i,j-1}}$, ce qui est impossible ; donc comme il est supposé qu'on a incrémenté ${\displaystyle j}$ au moins une fois, juste avant la dernière incrémentation de ${\displaystyle i}$, on a encore une autre incrémentation de ${\displaystyle i}$ avec ${\displaystyle p_{i-1,j}\leq \alpha _{i,i+1}\leq \alpha _{i-1,i}}$ ; il s'obtient alors par récurrence qu'on ne va jamais atteindre ${\displaystyle b_{j}}$ dans l'exécution de l'algorithme : contradiction. On a alors la première inégalité ${\displaystyle \beta _{j-1,j}>p_{i+1,j}}$. Aussi, comme la chaîne ${\displaystyle (a_{i+1},a_{i},b_{j})}$ est concave par hypothèse, on obtient directement ${\displaystyle p_{i+1,j}\leq \alpha _{i,i+1}}$. Donc, en incrémentant ${\displaystyle i}$ (de 1), on a bien les conditions ${\displaystyle p_{i,j}\leq \alpha _{i-1,i}}$ et ${\displaystyle p_{i,j}<\beta _{j-1,j}}$.

Ceci termine la preuve de la correction de l'algorithme.

On suppose que pour un ensemble initial de ${\displaystyle n}$ points du plan, cet algorithme de fusion est exécuté en temps ${\displaystyle O(n)}$. Ainsi, en notant ${\displaystyle C(n)}$ la complexité temporelle associée au calcul de l'enveloppe convexe de ${\displaystyle n}$ 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 :

${\displaystyle C(n)=2\times C(n/2)+O(n)}$

Par le master theorem ou par une analyse à la main, on conclut que ${\displaystyle C(n)}$ est en ${\displaystyle O(n\times \log _{2}(n))}$. Comme le tri d'un tableau (par exemple par tri fusion) peut être réalisé en temps ${\displaystyle O(n\times \log _{2}(n))}$, la complexité totale de l'algorithme est elle aussi en ${\displaystyle O(n\times \log _{2}(n))}$.

Il existe une autre façon de calculer l'enveloppe convexe de ${\displaystyle P}$ en calculant deux convexes non bornés dont l'intersection des deux donne l'enveloppe convexe final, 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.

• Calcul d'enveloppe convexe - Gestion dynamique d'une enveloppe convexe (enseignement de l'informatique à l'école Polytechnique de France)
• Fonctions convexes : inégalité des pentes

• Article original de Preparata et Hong - Convex Hulls of Finite Sets of Points in Two and Three Dimensions[1]
• Calcul de complexité : le Master theorem - Algorithms[2] (Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani) ; Introduction to algorithms[3] (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
• Calcul d'enveloppe convexe - Gestion dynamique d'une enveloppe convexe[4] (enseignement de l'informatique à l'école Polytechnique de France)

• Portail des mathématiques