Géométrie algorithmique

Rendu d'un cylindre à l'aide d'un programme d'ordinateur.

La géométrie algorithmique est le domaine de l' algorithmique qui traite des algorithmes manipulant des concepts géométriques.

La discipline qui a sans doute le plus contribué historiquement au développement de la géométrie algorithmique est l' infographie. Toutefois, à l'heure actuelle, la géométrie algorithmique se voit fréquemment impliquée dans des problèmes d'algorithmique générale.

Enveloppe convexe

Article détaillé : Calcul de l'enveloppe convexe.

L' enveloppe convexe d'un ensemble de points du plan est le plus petit polygone convexe contenant tous les points. Cette notion peut être immédiatement généralisée aux dimensions supérieures à 2.

Le meilleur algorithme connu actuellement permettant de déterminer l'enveloppe convexe d'un ensemble quelconque de n points en 2D (le parcours de Graham) ou 3D est en O(n log(n)). Sans connaissances additionnelles sur les données, on ne peut pas faire mieux que Ω(n log(n)) ; cependant, plusieurs algorithmes en O(n) existent pour traiter le cas de polygones simples (polygones non auto-intersectants) donnés dans l'ordre d'apparition des points. Il existe aussi des algorithmes où la complexité est donné en fonction du nombre de points n mais aussi en fonction du nombre h de points dans l'enveloppe convexe (i.e. la sortie de l'algorithme) ː la marche de Jarvis est un algorithme en O(nh) et l' algorithme de Chan est en O(n log h).

Dans le cas d'une dimension quelconque d (d > 3) les meilleurs algorithmes connus sont en .

Other Languages