Algorithme de Preparata-Hong

En algorithmique géométrique, l'algorithme de Preparata-Hong est une méthode algorithmique pour calculer l'enveloppe convexe d'un ensemble fini $P$ de points dans l'espace euclidien de dimension 2 (le plan) ou de dimension 3 (l’espace), mise au point par Franco Preparata et S. J. Hong. L'algorithme présente une stratégie utilisant le paradigme diviser pour régner. Cet article présente uniquement le cas de la dimension 2.

Description du problème

Exemple d'une enveloppe convexe de 16 points.

On considère un ensemble fini $P$ de points. On suppose sans perte de généralité que tous les points ont toutes leurs coordonnées différentes (si tel n'est pas le cas, on supprime les doublons). On cherche à trouver les sommets de son polygone convexe.

Principe en dimension 2

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

Cas de base

Le cas de base dans l’algorithme diviser pour régner survient lorsqu’il y a 1, 2 ou 3 points dans $P$. Dans ce cas, le calcul de l’enveloppe convexe est facile à calculer : il s'agit d'un point, d'un segment pour 2 points, d'un segment ou d'un triangle pour 3 points.

Cas récursif

S’il y a strictement plus de 3 points, on applique la stratégie diviser pour régner. Diviser : on commence par séparer l’ensemble des points en deux parties inférieure et supérieure de même cardinal à un point près. On note $P_{1}=\{x_{1},...,x_{\lfloor {\frac {n}{2}}\rfloor }\}$ et $P_{2}=\{x_{\lfloor {\frac {n}{2}}\rfloor +1},...,x_{n}\}$ les deux ensembles qui forment une partition de $P$ (on a pris pour $P_{1}$ la moitié plus éventuellement un des points de $P$ qui sont le plus "en bas" et $P_{2}$ le complémentaire de $P_{1}$ dans $P$, c'est-à-dire la moitié moins éventuellement un des points de $P$ qui sont le plus "en haut").

Régner : on calcule les enveloppes convexes respectives de $P_{1}$ et $P_{2}$. On appelle enveloppe convexe inférieur l'enveloppe convexe de $P_{1}$ et enveloppe convexe supérieur l'enveloppe convexe de $P_{2}$.

Ensuite, on vise à reconstruire l’enveloppe convexe globale à partir de ces enveloppes convexes inférieure et supérieure, en les reliant à la fois à gauche et à droite de la figure, par l’algorithme de fusion. À droite de la figure, on cherche à relier deux points provenant des parties inférieure et supérieure, en faisant en sorte que tous les points dans les deux parties soient à gauche de la droite tracée.

• 
  Les enveloppes convexes supérieure et inférieure à fusionner.
• 
  Jointure des enveloppes convexes.
• 
  L'enveloppe convexe finale fusionnée.

On applique pour cela l’algorithme suivant (on appelle $A$ et $B$ les parties inférieure et supérieure respectivement) :

• On part des points les plus à droite de chaque partie, $a$ pour $A$ et $b$ pour $B$,
• On cherche $a_{2}$ dans $A$ tel que la pente de $(a_{2},b)$ soit supérieure à la pente de $(a,b)$,
• On cherche $b_{2}$ dans $B$ tel que la pente de $(a_{2},b_{2})$ soit inférieure à la pente de $(a_{2},b)$,
• On itère jusqu’à rencontrer un blocage.

À la fin de cet algorithme, on relie les deux points dans $A$ et $B$ que l’on a trouvés. On réalise la même opération à gauche de $A$ et $B$, en adaptant l’algorithme ci-dessus, et on retire les arêtes superflues dans le nouveau polygone.

Algorithme de fusion dans le cas de la dimension 2

Détermination de la tangente à droite

     

 

Décrivons ici l'algorithme que l'on va utiliser pour fusionner les enveloppes convexes supérieure et inférieure. Soient $A$ et $B$ deux polygones convexes du plan euclidien. Soient $n,m$ des entiers strictement positifs, représentant respectivement le nombre de sommets de $A$ et de $B$. Soient $\{a_{1},...,a_{n}\}$ et $\{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 $r_{A}$ et $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 $C$, à partir de $A$ et $B$. Pour des raisons pratiques, on pourra raisonner sur les indices des sommets de $A$ et $B$ respectivement modulo $n$ et modulo $m$. Nous allons considérer que $x_{1}(a_{1})<x_{1}(b_{1})$ (le cas $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 $i=1,...,n$ et $j=1,...,m$, on note $p_{i,j}$ la pente de la droite $(a_{i},b_{j})$. Pour $i=1,...,n$ on note $\alpha _{i,i+1}$ la pente de la droite $(a_{i},a_{i+1})$ et pour $j=1,...,m$ on note $\beta _{j,j+1}$ la pente de la droite $(b_{j},b_{j+1})$. On note $g_{A}$ et $g_{B}$ respectivement les indices du sommet de $A$ le plus "à gauche" (celui d'abscisse la plus petite) et du sommet de $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 $C$. Voici le pseudo-code de l'algorithme, on notera $x_{1}(c)$ et $x_{2}(c)$ respectivement l'abscisse et l'ordonnée de $c$ où $c$ est un point du plan euclidien, et on suppose que les coordonnées des sommets de $A$ et $B$ et que les valeurs $\alpha _{i,i+1}$ pour $i=1,...,n$ et $\beta _{j,j+1}$ pour $j=1,...,m$ sont stockées dans des tableaux (accessibles à coût constant) :

Soient $i\leftarrow 1,j\leftarrow 1$

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

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

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

Renvoyer le couple $(i,j)$

Il est facile de voir que l'algorithme termine car on incrémente $i$ et $j$ de 1 si on doit recommencer à partir de la deuxième ligne de pseudo-code et dans le cas marginal où $i=g_{A}$ et $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 $O(g_{A}+g_{B})$, et donc en $O(n+m)$.

Correction de l'algorithme

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

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

ligne brisée convexe

• la suite $(\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 $(\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 qu'elle constitue bien un côté de l'enveloppe convexe issu de la fusion de $A$ et $B$) par :

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

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

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

• si $j^{*}=1$, alors $\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 $i^{*}$ dans $\{1,...,g_{A}\}$ et $j^{*}$ dans $\{1,...,g_{B}\}$ vérifiant la caractérisation ci-dessus.

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

• soit on a $(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 :

$(1)$ l'indice $j$ est le dernier indice auquel on a fait une incrémentation, auquel cas on avait $\beta _{j,j+1}>p_{i,j}>\alpha _{i,i+1}$ juste avant l'incrémentation, on a aussi $p_{i,j+1}\leq p_{i,j}$ (regarder le triangle $(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 $(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 $i$ (qui existe par hypothèse) et l'indice $j_{0}$ correspondant vérifie $p_{i,j_{0}}\leq \alpha _{i-1,i}$ (car l'incrémentation de $i$ indique de $p_{i-1,j_{0}}\leq \alpha _{i-1,i}$ et donc la chaîne $(a_{i},a_{i-1},b_{j_{0}})$ est concave), par la chaîne d'inégalité on a bien $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 $(a_{i},b_{j+1},b_{j})$) cela donne $\beta _{j,j+1}>p_{i,j+1}$ : en incrémentant $j$ (de 1), on a finalement les conditions $p_{i,j}\leq \alpha _{i,i-1}$ et $p_{i,j}<\beta _{j-1,j}$ ;

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

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

Complexité temporelle de l’algorithme

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

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

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

Une autre approche du problème

Il existe une autre façon de calculer l'enveloppe convexe de $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^{[réf. nécessaire]}.

Liens externes

• 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

Sources

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