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 $P$ 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. 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

Exemple d'une enveloppe convexe de 16 points.

On considère un ensemble fini $P$ de $n$ 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 $P$.

Principe en dimension 2

On commence par trier les points de $P$ dans l'ordre croissant selon la dernière (c'est-à-dire la deuxième) coordonnée. Soit $(x_1,...,x_n)$ la liste des points de $P$ après ce tri.

Premiers cas

Les premiers cas de l’algorithme diviser pour régner sont ceux où il y a 1, 2 ou 3 points dans $P$. 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

S’il y a strictement plus de 3 points, on applique la stratégie diviser pour régner. « 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 $A=\{x_1,...,x_{\lceil \frac{n}{2}\rceil }\}$ et $B=\{x_{\lceil \frac{n}{2}\rceil +1},...,x_n\}$ les deux sous-ensembles obtenus ; ils forment une partition de $P$. À cause de la convention d'ordonnancement des points, les premiers points du tri ont les deuxièmes coordonnées les plus petites, et $A$ est donc la moitié (plus éventuellement un point) des points de $P$ dont les ordonnées sont les plus petites, c'est-à-dire qui sont le plus « bas » dans une représentation plane. De même, $B$, le complémentaire de $A$ dans $P$, comprend les points de $P$ 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 $A$ et $B$. On appelle pour simplifier « enveloppe convexe inférieure » l'enveloppe convexe de $A$ et « enveloppe convexe supérieure » l'enveloppe convexe de $B$. 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 $P$, 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 :

• 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 $a$ le plus à droite dans $A$ et $b$ le plus à droite dans $B$,
• On cherche $a_2$ dans $A$ tel que la pente de la droite $(a_2,b)$ soit supérieure à la pente de la droite $(a,b)$,
• On cherche $b_2$ dans $B$ tel que la pente de la droite $(a_2,b_2)$ soit inférieure à la pente de la droite $(a_2,b)$,
• On itère jusqu’à rencontrer un blocage.

À la fin de cet algorithme, on relie les deux derniers points trouvés, dans $A$ et $B$ respectivement.

On réalise ensuite la même opération à gauche de $A$ et $B$, 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 $P$.

Algorithme de fusion dans le cas de la dimension 2

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}\ge 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 à chaque fois que l'on doit recommencer à partir de la ligne $(***)$ du pseudo-code ; dans le cas marginal où $i=g_A$ et $j=g_B$, 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 $O(g_A+g_B)$, et donc de l'ordre de $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^{*}\ne g_A$ et $j^{*}\ne g_B$.

ligne brisée convexe

Grâce à la convexité de $A$ et $B$, on remarque que les suites $({\alpha }_{1,2},...,{\alpha }_{g_A-1,g_A})$ et $({\beta }_{1,2},...,{\beta }_{g_B-1,g_B})$ sont décroissantes (la concaténation des segments associés est 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 pour qu'elle constitue bien un côté de l'enveloppe convexe issu de la fusion de $A$ et $B$) de la manière suivante :

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

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

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

• si $j^{*}=1$, alors ${\beta }_{1,2}\le 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}\le 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=1etj>1)ou(i>1etj=1)$ 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 :

$(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}\le 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}\le {\alpha }_{i-1,i}$ (car l'incrémentation de $i$ indique de $p_{i-1,j_0}\le {\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}\le {\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}\le {\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}\ge p_{i,j}$. De même on ne peut pas avoir ${\beta }_{j-1,j}\le 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}\ge 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}\ge 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}\ge 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}\le {\alpha }_{i,i+1}\le {\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}\le {\alpha }_{i,i+1}$. Donc, en incrémentant $i$ (de 1), on a bien les conditions $p_{i,j}\le {\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 theoremModèle:, 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 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.

Voir aussi

Articles connexes

• Calcul de l'enveloppe convexe
• Algorithme de tri
• Théorème sur les récurrences de partition

Liens externes

• Modèle:Lien web.