Les enveloppes convexes

Algorithmique > Enveloppes convexes [ Commenter ]

Description du problème

Soit un ensemble Γ de points du plan. Le but est de trouver le plus petit polygône convexe Ρ qui comprend tous les points de Γ, c'est-à-dire celui dont le périmètre est le plus petit possible.

Soit n le nombre de points de Γ, et h le nombre de points de Γ appartenant à Ρ (c'est-à-dire le nombre de sommets de Ρ).

Algorithmes

• Enveloppe convexe rapide - compléxité en Ω(n.log(n))
• Recherche de Graham - complexité en Ω(n.log(n))
• Marche de Jarvis - compléxité en Ω(n.h), donc Ω(n²) dans le pire des cas