Algorithmes de calcul d'enveloppe convexe

TBD expliciter les divers formes d'algorithme (diviser pour régner, gloutons, etc)

Les algorithmes de recherche d'enveloppes convexes d'ensembles de points de $\mathbb{R}^2$ font partie, comme les algorithmes de tri, des problèmes qu'adorent les algorithmiciens. Ces problèmes peuvent en effet se résoudre de multiples manières et les algorithmes résultant sont à la fois ingénieux et élégants. Ils sont cependant souvent plus compliqués que les algorithmes de tris.

Nous allons ici montrer quelques uns de ces algorithmes, les plus connus. Mais avant de rentrer dans le vif, commençons par définir le problème.

Convexité

La notion de convexité, très générale, est utilisée lorsque l'on manipule des objets pleins et de forme bombée. Elle se formalise en utilisant les segments :

De nombreux problèmes d'optimisations deviennent facile lorsque l'objet étudié (fonction, ensemble, forme géométrique, etc) est convexe.

Fonction convexe

Pour une fonction convexe, pour tous couples de points $A = (x, f(x))$ et $B = (x', f(x'))$, quelque soit $(u, v) \in [A, B]$ on a $v \geq f(u)$ (le segment est au dessus de la courbe) :

Les fonctions convexes sont sympathiques en optimisation car tout minimum local est un minimum global. Il est donc très facile avec une méthode de gradient de trouver son minimum.

Ensemble convexe

La première propriété que l'on peut donner est, clairement, que :

Les ensembles convexes sont en forme de patate et en tout point, la tangente est à l'extérieur de l'ensemble :

Les ensembles non convexes vont avoir une forme de haricot. Il va exister des points où la tangente traversera la forme (en bleu) et des segments qui ne sont pas inclus dans l'ensemble et dont les extrémités sont dans l'ensemble (en rouge) :

Les ensembles convexes ont de fortes propriétés de stabilité :

Comme l'ensemble $\mathbb{R}^2$ est convexe, on déduit de la proposition précédente que :

Les ensembles convexes ont de multiples propriétés mathématiques sympathiques très utiles en topologie. Ils sont également très utiles en optimisation sous la forme particulière des polygones convexes.

Polygone convexe

En informatique (et dans la vie réelle), les ensembles convexes se rencontrent uniquement sous la forme de polygones convexes.

Un polygone simple est une surface :

Un polygone convexe est un polygone simple particulier :

Quelques exemples de polygones non convexes (polygone croisé à gauche et angle supérieur à 180 à droite):

Bien sûr :

Les polygones convexes sont très utilisés en infographie car ils permettent de calculer très rapidement des intersections entre :

• un polygone convexe et une droite, ce qui est crucial en raytracing
• deux polygones convexes, ce qui est indispensable pour des calculs rapides de collisions pour des jeux 2D

Enfin, les problèmes d'optimisation linéaire se résolvent facilement car cela revient à trouver un maximum dans un polygone convexe.

Par exemple :

Enveloppe convexe

Lorsque l'on se place dans $\mathbb{R}^n$ (ou plus généralement dans un espace affine réel), la définition précédente est équivalente à la définition ci-dessous :

On peut même aller plus loin lorsque nos points sont dans $\mathbb{R}^2$ (dans le cas général, il suffit que l'espace soit de dimension fini) :

L'enveloppe convexe d'un ensemble fini de points de $\mathbb{R}^2$ comme celui-ci :

est l'union de ses triangles :

On peut maintenant conclure :

Pour l'exemple précédent :

Notez qu'une fois que l'enveloppe convexe est déterminée, il est facile de trouver un ensemble de triangles extrémaux (la solution n'est unique) en parcourant les points :

Quelques problèmes de polygones

Avant de partir bille en tête sur les algorithmes de construction d'enveloppe convexe, commençons par résoudre quelques problèmes connexes, qui permettrons de nous échauffer et qui seront bien utiles plus tard.

Droite, points et segments

Une droite coupe l'espace en deux demi-plans (rouge et vert dans la figure ci-dessus). Comment savoir efficacement dans quel demi plan se trouve un point ?

Une possibilité efficace est de regarder l'angle fait par un vecteur directeur de la droite ($\overrightarrow{ab}$ dans la figure ci-dessous) et un autre vecteur dont une extrémité est le point dont on veut connaître le demo-plan et l'autre un point de la droite ($\overrightarrow{au}$ et $\overrightarrow{av}$ dans la figure ci-dessous) :

En considérant le sens trigonométrique (anti-horaire) et des angles entre -180 et 180 degrés, le demi-plan vert a un angle négatif et le demi-plan rouge un angle positif.

Le calcul du signe de l'angle est de plus très simple !

Remarquez que le calcul du signe de l'angle ne requiert que 2 multiplications et 1 soustractions, ce qui se fait donc extrêmement rapidement !

Le signe du déterminant est lié aux droites. Considérons les points $a$ et $b$ de la figure précédente. Si le vecteur $\overrightarrow{ab}$ est de coordonnée $(x, y)$, le vecteur $\overrightarrow{ab}^\perp = (-y, x)$ est orthogonal à $\overrightarrow{ab}$ et l'équation de la droite $(a, b)$ est :

$$ \overrightarrow{ab}^\perp \cdot \overrightarrow{ax} = 0 $$

Ce qui s'écrit, si $a=(a^x, a^y)$ et $b=(b^x, b^y)$ :

Si un point $(x, y)$ n'est pas sur la droite alors :

• $Ax + By + C > 0$ s'il est dans le demi-plan rouge
• $Ax + By + C < 0$ s'il est dans le demi-plan vert

Reconnaissance de polygones

Soit $P = [p_1, \dots, p_h]$ un polygone ($p_i = (p_i^x, p_i^y)$ pour tout $1\leq i \leq h$).

Est-il simple ? Convexe ?

Polygone simple

Nous allons dans la suite nous concentrer sur les polygones simples. Mais comment savoir si un polygone donné l'est ?

de i allant de 1 à h-2:
   de j allant de i+2 à h:
      vérifier que les segments [p[i], p[i+1]] et [p[j], p[(j+1) % h]] ne se croisent pas

Polygone simple convexe

Supposons que le polygone $P$ est simple. Est-il convexe ?

Là encore, la solution est très simple en utilisant les vecteurs :

De la proposition précédente on peut déduire :

Polygones convexes

Nous allons montrer ici quelques propriétés sympathiques des polygones convexes.

Dans toute cette partie on considère que $P = [p_1, \dots, p_h]$ est un polygone convexe ($p_i = (p_i^x, p_i^y)$ pour tout $1\leq i \leq h$) donné dans le sens horaire.

Min / Max

Tout se passe comme si les points du polygone étaient triés ! Trouver le minimum est donc très rapide.

Tangentes

À tout point extérieur à un polygone convexe passe deux tangentes :

L'une pour laquelle tous les points du polygone sont à sa droite (la droite verte), l'autre pour laquelle tous les points du polygone sont à gauche (la droite rouge).

Un corollaire à cet exercice est que l'on peut déterminer si une droite intersecte un polygone convexe en $\mathcal{O}(\log(h))$ opérations. Il suffit en effet de prendre un sommet de la droite qui n'est pas sur le polygone (d’abscisse inférieure au minimum) puis de calculer les tangentes. si la pente de la droite n'est pas dans l'angle formé par les deux tangentes, elle ne coupe pas le polygone.

Dedans ou dehors ?

Le dernier problème que nous allons aborder est de savoir si un point est dans le polygone convexe ou pas.

Commençons simplement :

Sans surprise :

Conclusion

Les polygones convexes permettent de calculer très efficacement :

• des minimaux ou des maximaux
• des intersections :
  • entre droite et polygone convexe
  • entre deux polygones convexes (au moins un sommet d'un polygone est à l'intérieur de l'autre)

Ils sont pour cela très utilisé en infographie pour :

• du raytracing : le rayon rebondi sur le polygone selon la normale du segment qu'il intersecte (remarquez que la normale pointe vers l'extérieur)
• dans les jeu car le calcul de la collision est rapide

Problème de l'enveloppe convexe

Le vif du sujet :

Pour alléger les algorithmes, on considérera que tous les points de $\mathcal{P}$ sont position générale, c'est à dire que trois points de $\mathcal{P}$ ne sont pas alignés.

Reconnaissance

En utilisant ce que nous avons fait précédemment, il est facile de savoir si un polygone convexe $P = [p_1, \dots, p_h]$ est l'enveloppe convexe de $\mathcal{P}$ :

• on vérifie pour chaque point en $\mathcal{O}(\log(h))$ s'il est dans le convexe
• lors de la vérification d'un point, on pourra également savoir si c'est un point du polygone. Si à la fin de la vérification, on a $h$ points sur l'enveloppe, tous les points de $P$ sont dans $\mathcal{P}$

On conclut de ce qui précède que :

Marche de Jarvis

Le principe de la marche de Jarvis est simple : construire l'enveloppe convexe de façon gloutonne. Il utilise pour cela la proposition suivante :

Régime stable

Supposons que l'on ait déjà déjà commencé à construire l'enveloppe convexe en ayant les $i > 1$ premiers points : $[p_1, \dots, p_i]$

On balaie tous les points et le prochain élément sur l'enveloppe sera celui qui maximisera l'angle avec le point précédent. ce qui revient à trouver le point $x$ maximisant :

Ce point $x$ est le seul point différent de $p_{i-1}$ tel que la droite $(p_i, x)$ place tous les éléments de $P$ à sa droite : c'est le prochain élément de l'enveloppe.

Initialisation

On sait que les points réalisant le minimum des abscisses sont sur l'enveloppe convexe (il y en a au plus 2 si les points sont en position générale): on en prend un pour être $p_1$.

Choisir $p_2$ revient à trouver le point minimisant l'angle avec l'axe des ordonnées.

Fin

L'algorithme s'arrête lorsque l'on boucle sur $p_1$

Complexité

Cette complexité n'est pas usuelle puisqu'elle combine à la fois une donnée liée à l'entrée (le nombre $n$ de points) et une donnée liée à la sortie (la taille $h$ de l'enveloppe convexe).

La taille de l'enveloppe convexe est très variable, elle peut aller de 3 (figure de gauche) à $n$ (figure de droite) :

On en conclut que :

Même si souvent la taille de l'enveloppe convexe est plus petite que $n$.

Complexité du problème

On montre que le problème du tri est un cas particulier du problème de l'enveloppe convexe.

Soit $L=[x_1, \dots, x_n]$ une liste de $n$ nombres que l'on veut trier et considérons les $n$ points $\mathcal{P} = \{ (x_1, x_1^2), \dots, (x_i, x_i^2), \dots, (x_n, x_n^2)\}$

Tout se passe comme si on avait placer les points à trier sur une parabole.

De là, l'enveloppe convexe des points est :

Une fois le maximum des points trouvé (en $\mathcal{O}(\log(n))$ opération), suivre l'enveloppe c'est trier les points par ordre décroissant.

Comme l'algorithme suivant atteint cette borne, on peut écrire :

Notez que notre transformation admet d'autres bornes possibles si on prend en compte le nombre d'éléments $h$ de l'enveloppe, par exemple $\mathcal{O}(h\log(h))$ ou encore $\mathcal{O}(n\log(h))$.

Parcours de Graham

Le parcours de Graham fonctionne en deux temps. Il commence par ordonner les points pour construire un polygone simple particulier. Ce polygone sera ensuite raffiné pour obtenir un polygone convexe.

Polygone simple particulier

L'algorithme commence par trouver le point d’abscisse minimum qu'on nomme $p_1$, puis il trie tous les sommets $x$ par angle $\theta$ croissant :

On construit ensuite le polygone simple en relier les points dans cet ordre :

Ce polygone n'est pas convexe mais :

1. il est simple
2. dans le cône formé par $p_1$ et deux sommets successifs, il n'y a aucun autre sommet

Simplification de Sklansky

La simplification de Sklansky procède comme sur la figure ci-dessous :

On parcours les points dans l'ordre du polygone et si l'angle intérieur $(p_{i-1}, p_i, p_{i+1})$ n'est pas bon :

1. on supprime $p_i$ du polygone
2. i = i-1
3. on continue la procédure de vérification avec le le nouveau $p_i$ (qui était $p_{i-1}$ à l'étape précédente)

Au final, tout les sommets du polygone sont vérifiés et dans le cas du polygone simple obtenu par Graham on obtient :

Le polygone est bien convexe.

Dans le cas de du polygone obtenu par l'algorithme de Graham, comme les cônes vides entre deux sommets successifs assurent qu'il n'y aura jamais de croisement de segments et donc que la simplification de Sklansky va fonctionner et donner un polygone convexe en fin de simplification.

Cette simplification va vite !

La simplification de Sklansky était à l'origine un algorithme proposé pour trouver l'enveloppe convexe d'un polygone simple. Il a cependant rapidement été prouvé faux. Il existe des algorithme linéaires pour trouver l'enveloppe convexe d'un polygone simple (comme l'algorithme de Melkan) mais ils sont bien plus ardu à implémenter. Autant s'en passer si la simplification de Sklansky fonctionne (on le rappelle, elle ne fonctionne qui si on ne produit jamais de croisements).

Complexité

La complexité du parcours de Graham réside dans le tri :

Selon la taille de l'enveloppe convexe, cette complexité sera plus ou moins grande que l'algorithme de Jarvis.

Le suspens est insoutenable. Existe-t-il de meilleurs algorithmes que ces deux là ? Avant de répondre (oui) à cette épineuse question regardons un algorithme dont la complexité en moyenne est linéaire.

Les divisions de Préa

On doit cet algorithme à Préa (1995), publié dans son poly d'Algorithmie de l'école centrale marseille méditerranée. Il ressemble à l'algorithme Quickhull, mais le calcul de ses complexités, en particulier en moyenne est cependant plus simple.

fonction diviser(P):
    soit p le point de P d'ordonnée maximum
    soit q le point de P d'ordonnée minimum

    Soient G les points de P strictement à gauche de la droite (p, q)
    Soient D les points de P strictement à droite de la droite (p, q)

    return p, q, G, D

fonction simplifier(p, q, p', q'):
    si p' est dans le triangle qq'p alors :
        p' = p
    si q' est dans le triangle qp'p alors :
        q' = q

    return p', q'

fonction convexe(P):
    p,q, G, D = diviser(P)

    P = [p]
    Q = [q]

    Tant que D est non vide:
        p' ,q', G, D = diviser(D)
        p', q' = simplifier(p, q, p', q')

        ajoute p à la fin de P
        si q ≠ p:
            ajoute q au début de Q

    Tant que G est non vide:
        p', q', G, D = diviser(G)
        p', q' = simplifier(p, q, p', q')

        ajoute p au début de P
        si q ≠ p:
            ajoute q à la fin de Q

    C = P + Q
    Faire une simplification de Sklansky sur C

    rendre C

L'algorithme va séparer l'espace en 2 à chaque appel de diviser et ne va garder que le demi-espace utile.

Par exemple :

Au bout d'un diviser à droite et un diviser à gauche, tous les points inutiles ont été supprimés. Après la seconde passe, on a obtenu l'enveloppe convexe. L'étape de simplification (ci après une simplification à droite. Le procédé est similaire pour une simplification à gauche et si la pente $(p, q)4 est inversée), permet de minimiser le nombre de points restant et donc de s'assurer une complexité moyenne faible (les points dons les triangles ne sont jamais sur l'enveloppe convexe) :

L'étape de simplification est locale, il se peut donc que globalement, le polygone C obtenu par divisions successives (ligne 27) ne soit tout de même pas convexe :

Il est cependant simple et une simplification de Sklansky ne va jamais produire de croisement. En effet, entre 2 points successifs, il existe une bande horizontale sans points qui correspond à la différence entre les 2 max ou min successifs :

L'argument donné pour le parcours de Graham peut donc être réutilisé ici pour montrer que la simplification de Sklansky va bien se passer. Cette étape de raffinage prend alors au pire $\mathcal{O}(n)$ opérations.

Les boucles while des lignes 24 et 32 peuvent dans le cas le pire des cas n'éliminer aucun point différents de p et q (si on veut trouver l'enveloppe convexe d'un zèbre par exemple) :

De là :

La complexité n'est donc pas terrible pour cet algorithme. En revanche, sa complexité en moyenne est très bonne.

En effet, chaque appel à diviser va supprimer une fraction des points. Si cette fraction est proportionnelle à $n$, disons $\alpha \cdot n$ avec $0 < \alpha \leq 1$ la complexité $T(n)$ de chaque boucle while respectera l'équation :

$$ T(n) = \mathcal{O}(n) + T((1-\alpha)\cdot n) $$

Comme $\frac{1}{1-\alpha} > 1$, cette équation peut être résolue avec le master theorem et on obtient : $T(n) = \mathcal{O}(n)$.

Il nous reste à montrer que c'est bien vrai :

Cet algorithme est donc très efficace lorsque les données sont répartis de façon homogène dans le plan.

Combinaisons d'enveloppes convexes

Pour l'instant, nous avons chercher l'enveloppe convexe à un ensemble de points. Regardons le problème connexe :

Nous allons montrer deux méthodes pour le faire. Mais avant de commencer, remarquez que :

Enveloppes disjointes

Si les enveloppes connexes sont disjointes, on peut supposer sans perte de généralité qu'il existe une droite verticale les séparant (à un rotation prêt) :

On peut alors chercher le point le plus à droite du polygone de gauche (point vert) et le point le plus à gauche du polygone de droite (point rouge).

On construit alors le polygone de la figure ci-dessous, en simulant une double jonctions entre les sommets rouge et vert, une jonction permettant d'aller de gauche à droite et l'autre de droite à gauche.

Ce polygone est simple et on peut utiliser une simplification de Sklansky pour le rendre convexe :

La complexité totale de cette jonction est en :

• recherche des éléments extrémaux des deux polygones : $\mathcal{O}(h_1 +h_2)$
• simplification de Sklansky : $\mathcal{O}(h_1 + h_2)$

Enveloppes quelconques

Il est impossible d'utiliser la même technique que précédemment car il est impossible de combiner les deux polygones convexe en un polygone simple que l'on pourra simplifier avec Sklansky.

On peut en revanche utiliser une marche de Jarvis pour créer la nouvelle enveloppe.

On suppose que la première enveloppe est $P_1 = [p^1_1, \dots, p^1_{h_1}]$, la seconde $P_2 = [p^2_1, \dots, p^2_{h_2}]$ et que l'on construit l'enveloppe $P = [p_1, \dots, p_h]$.

On commence par le point le plus à gauche des deux enveloppes. Ce point est nécessairement dans l'enveloppe globale.

Soit $p_i$ le dernier point ajouté à l'enveloppe convexe. Le point suivant de la marche de Jarvis est celui maximisant l'angle avant l'axe des ordonnés si $i=1$ ou la droite $(p_{i-1}, p_i)$ sinon.

Supposons que $p_i$ soit le point $p^1_j$ du polygone $P_1$ :

• le point de $P_1$ maximisant l'angle est $p^1_{j+1}$
• le point de $P_2$ maximisant l'angle est $p^2_{k}$ tel que la droite $(p_i, p^2_{k})$ soit tangente à $P_2$ et place tous ses éléments à sa droite. Ce point se trouve en $\mathcal{O}(\log(h_2))$ opérations.

Le prochain point $p_{i+1}$ est donc soit $p^1_{j+1}$ soit $p^2_{k}$.

Trouver $p_{i+1}$ se trouve donc en $\mathcal{O}(\log(h_1))$ ou en $\mathcal{O}(\log(h_2))$ selon l'enveloppe convexe sur laquelle se trouve $p_i$. Comme tous les points de $P_1$ et tous les points de $P_2$ peuvent faire parti de l'enveloppe finale, on a :

Cette complexité dépend de la taille de la sortie. Elle est donc plus importante que la première méthode lorsque $h$ est de l'ordre de $h_1 + h2$ mais plus petite lorsque $h$ est petit.

Algorithmes diviser pour régner

Le principe de l'algorithme diviser pour régner est toujours le même :

1. on sépare le problème en deux sous problèmes : ici on partitionne l'ensemble de points $\mathcal{P}$ en deux parties $\mathcal{P}_1$ et $\mathcal{P}_2$
2. on résout chaque partie séparément (en utilisant le même algorithme)
3. on recolle les deux solutions partielles - ici les deux enveloppes convexes $P_1$ et $P_2$ - en une unique enveloppe convexe $P$

Les algorithmes diviser pour régner sont efficaces lorsque le recollement des solutions partielle en une solution globale (partie 3) est simple à effectuer, puisque la complexité de l'algorithme répond à l'équation de récurrence ($\sum_k n_k \leq n$) :

Dont la solution est donnée par le master theorem.

Nous allons montrer deux méthodes et comparer leurs complexités.

Méthode 1 : polygones disjoints

Pour s'assurer que les deux enveloppes convexes $P_1$ et $P_2$ soient disjoints, on commence par trier les points de $\mathcal{P}$ par abscisses croissantes, ce qui permet de toujours séparer en deux parties séparées par un axe vertical.

On peux alors utiliser la méthode de recollement pour polygones disjoints vues précédemment pour obtenir une complexité :

$$ C(n) = \mathcal{O}(n) + 2\cdot C(\frac{n}{2}) $$

Le master theorem nous indique que cette complexité vaut : $C(n) = n\log(n)$.

Le tri initial des points (en $\mathcal{O}(n\log(n))$ opérations) n'a pas dégradé la complexité :

Méthode 2 : polygones convexes quelconques

Si l'on utilise des polygones quelconques, on a pas besoin de trier les éléments au début, mais chaque recollement coûte pus cher dans le cas le pire. On obtient une équation de complexité valant :

$$ C(n) = \mathcal{O}(n\log(n)) + 2\cdot C(\frac{n}{2}) $$

L'énoncé général du master theorem nous donne alors une complexité totale de $C(n) = \mathcal{O}(n\log^2(n))$. Ce qui est - c'était attendu - pire (mais pas de beaucoup) de la méthode 1.

Algorithme optimal

L'algorithme que allons maintenant présenter est de complexité $\mathcal{O}(n\log(h))$ où $n$ est le nombre de points et $h$ la taille de l'enveloppe convexe résultante.

Cette complexité est la meilleure complexité connue.

1. partitionnez les $n$ points en $\frac{n}{m}$ paquets de $m$ points. Coût de cette étape : $\mathcal{O}(n)$
2. trouver avec le parcours de Graham l'enveloppe convexe de chaque paquet en $\mathcal{O}(m\log(m))$ opérations. Coût de cette étape : $\mathcal{O}(\frac{n}{m}m\log(m)) = \mathcal{O}(\frac{n}\log(m))$ opérations
3. Trouver l'enveloppe convexe globale en utilisant la marche de Jarvis (la méthode 2) :
   1. le premier point est le point tout à gauche : $\mathcal{O}(n)$ opérations
   2. trouver le prochain élément de la marche prend $\mathcal{O}(\frac{n}{m}\log(m))$ opérations car il y a $\frac{n}{m}$ enveloppes et la taille de l'enveloppe convexe de chaque enveloppe est au maximum $m$
   3. au total, trouver l'enveloppe convexe prend : $\mathcal{O}(h\frac{n}{m}\log(m))$ opération

Pour un $m$ donné, cet algorithme prend un nombre d'opérations de l'ordre de :

$$ \mathcal{O}(n + n\log(m) + h\cdot \frac{n}{m}\log(m)) = \mathcal{O}(n\log(m) + h\cdot \frac{n}{m}\log(m)) $$

• Si $m = h$ l'algorithme prend $\mathcal{O}(n\log(h))$ opérations
• Si $m < h$ alors $n\log(m) < h\cdot \frac{n}{m}\log(m)$ et l'algorithme prend de l'ordre de $h\cdot \frac{n}{m}\log(m)$ opérations
• Si $m > h$ alors $n\log(m) > h\cdot \frac{n}{m}\log(m)$ et l'algorithme prend de l'ordre de $\mathcal{O}(n\log(m))$ opérations

La complexité minimale de cet algorithme est ainsi atteinte pour $m=h$. Le soucis est que l'on ne connaît pas $h$. Mais lors de la marche de Jarvis au bout de $m$ itérations on sait si on a fini ou non.

L'idée est alors de ne faire que $m$ étapes de la marche pour un $m$ donné. La complexité de cet algorithme tronqué est alors toujours en : $\mathcal{O}(n\log(m))$. On a deux cas :

• soit $m$ est plus petit que $h$. On aura pas construit l'enveloppe convexe car on ne sera pas revenu au point de départ de la marche
• soit $m$ est plus grand que $h$. On aura construit l'enveloppe convexe car on sera revenu au point de départ de la marche à une étape donnée. On pourra alors stopper l'algorithme à ce moment là.

On itère alors cet algorithme en commençant par un $m$ petit que l'on fait croître tant que l'on a pas réussi à construire l'enveloppe convexe. La ruse ultime est de faire croître $m$ pas trop lentement pour ne pas faire trop d'itérations et pas trop rapidement pour avoir de trop d'ensembles (on en a $m$) à considérer. On prend $m_1 = 4$ et $m_{i+1} = m_i^2$.

Explicitons le calcul de la complexité.

On montre facilement que $m_i = 2^{2^i}$ et que le premier $m_{i^\star} \geq h$ est tel que $m_{i^\star} < h^2$ donc :

Le nombre total d'opérations effectuées par l'algorithme est alors :