Algorithme en nlog(n) ... pas mieux ??

Bonjour, je me présente je suis étudiant et nous faisons actuellement avec quelques camarades de promotion des recherches sur les algorithmes de recherche d'enveloppes convexes. Il nous a été dit qu'on ne "pouvait pas faire mieux qu'un algorithme en n*log(n)" en parlant des algorithmes de Graham et QuickHull. Il nous a été aussi dit que cela se montrait. Et nous cherchons cette démonstration que je n'ai pas trouvé sur google (ni ailleurs).

Pourriez vous nous aider ?? (URL, bouquin .... enfin n'importe quelle référence quoi ...)

La complexité du calcul d'une enveloppe convexe dépend des données de départ et de la dimension dans laquelle on travaille.

En 2D (je suppose que c'est le cas ici), si on part d'un polygone non auto-intersectant on peut calculer l'enveloppe convexe en O(n). Dans le cas général (nuage de points sans ordre particulier) l'algorithme optimal est effectivement en O(n * log(n)). C'est aussi vrai en 3D.

Un petit coup de Google pour la démonstration et hop : http://www-2.cs.cmu.edu/afs/cs/user/...n/conv_hul.pdf

Théorème : La construction de l'envelopppe convexe de N points est en
\Gamma(N log n)

Preuve (il y a une certaine beauté je trouve) :
On suppose qu'on a un algorithme A permettant de construire une eneveloppe convexe pour définir un algorithme de tri B.

Algo B : Soient x1, ...,xn n réels à trier
On considère les points p1(x1, x1^2), p2(x2, x2^2), ..., pn(xn, xn^2)
Les pi sont sur la courbe y = x^2

On appelle l'algorithme A sur les points : p1, ..., pn qui retourne l'enveloppe convexe de ces points (dont tous ces points sont des sommets). Cette enveloppe convexe est un polygone covenxe ; les points sont tous consécutifs, donc d'absisses croissantes. Il suffit de retourner les abscisses qui sont ordonnées

Complexité de B : O(N) + complexité de A
or B est un algo de tri, donc sa complexité ne peut être inférieur à
\Gamma(N log N) (pour un tri par comparaison)
Par conséquent, O(N) + C(A) => \Gamme(N log N)
Donc la complexité est supérieur à \Gamma(N log N)

Citation:

---

Envoyé par nicolas581

Théorème : La construction de l'envelopppe convexe de N points est en \Gamma(N log n)

---

C'est la première fois que je vois noté \Gamma la complexité d'un algorithme. En général c'est plutôt O ou \Omega.

Sinon un petit complément (chipotage ?) pour terminer la preuve :
La démonstration ci dessus donne une borne inférieure. Mais comme on peut exhiber des algorithmes atteignants cette borne inférieur, la complexité est exactement en O(N log N).

Citation:

---

Envoyé par sovitec

C'est la première fois que je vois noté \Gamma la complexité d'un algorithme. En général c'est plutôt O ou \Omega.

---

Oui autant pour moi c'est \Omega que je voulais mettre, le soir je suis fatigué pour faire de l'algo errare humanum est :) .

Citation:

---

Envoyé par sovitec

Mais comme on peut exhiber des algorithmes atteignant cette borne inférieure, la complexité est exactement en O(N log N).

---

\begin{chipotage}
Dans ce cas tu peux écrire \Theta(N log N)
\Omega => borne inf
O => bore sup
\Omega(N log N) <= \Theta <= \O(N log N)
\end{chipotage}

PS : la question posée était montrer qu'on ne peut pas faire mieux, donc une borne inf suffit. Néanmoins ta remarque complémentaire est juste, qui a dit "inutile" ;) pour la question. Il faut répondre aux questions uniquement aux questions. Ainsi en essayant de répondre un peu plus lors de nos exams d'algo on arrivait jamais à finir, en un mot il faut aller à l'essentiel.

Merci beaucoup !!