Géométrie algorithmique

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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.

Définition et premiers exemples[modifier | modifier le code]

La géométrie algorithmique est l'étude des agorithmes qui manipulent des objets géométriques. Par exemple, le problème algorithmique qui consiste, étant donné un ensemble de points dans le plan, décrit par leurs coordonnées, à trouver les deux points les plus proches l'un de l'autre, est un problème l'algorithmique géométrique.

Histoire et utilisations[modifier | modifier le code]

L'une des origines de la discipline est le fait que des modèles informatique, c'est-à-dire de la réalité virtuelle, remplace les maquette dans la conception d'objets, à partir des années 1970[1]. Ces modèles permettent ensuite l'étude d'une grande diversité de phénomène du monde réel[2]. 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.

La géométrie algorithmique est aujourd'hui utilisée en inforgraphie, en robotique, pour les systèmes d'information géographique, et la conception par ordinateur[1].

Structure de données classiques[modifier | modifier le code]

Certaines structures, qui apparaissent ou bien dans l'entrée du problème, ou bien à l'intérieur de l'algorithme sont centrales en géométrie algorihtmique : les polyèdres, les diagramme de Voronoï, et les triangulations[2].

Problèmes classiques[modifier | modifier le code]

Enveloppe convexe[modifier | modifier le code]

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 .

Problèmes d'algorithmique générale[modifier | modifier le code]

La géométrie algorithmique fournit des solutions optimales pour des problèmes décrits sur un univers borné. En effet, celle-ci traite de problèmes énoncés en termes de points disposés sur une grille bornée [1, X] × [1, Y] de dimension 2. Par extension, elle traite ces mêmes problèmes sur des grilles de dimensions supérieures et sur des intervalles d'entiers (dimension 1).

Par exemple, étant donné un ensemble de points S dans l'intervalle d'entiers [1, U], il est possible de tirer profit du caractère borné de l'univers [1, U] pour résoudre certains problèmes en dessous de leur complexité minimale pour un univers non borné. Le cas le plus trivial et le plus connu est celui du tri linéaire, le bucket sort. Les éléments de S peuvent être triés en temps |S|+ U en parcourant S une première fois et en stockant chaque élément trouvé dans le « seau » correspondant dans une série de seaux numérotés de 1 à U.

De très nombreux problèmes d'algorithmique trouvent des solutions optimales dans un univers borné :

  • Étant donné un ensemble S de cardinal n sur un intervalle entier [1, U],
    • Récupérer l'élément de S le plus proche d'un x donné en temps au lieu de log(n) grâce à la structure de q-fast-trie.
  • Étant donné un ensemble S sur une grille [1, U] x [1, U].
    • Récupérer tous les points qui dominent un point x sur leurs deux coordonnées en temps k + log(log(U)) si k est le nombre de réponses, au lieu de k+log(n). Voir aussi recherche par plage (range searching).
  • Étant donné un ensemble I d'intervalles sur l'intervalle [1, U],
    • Retrouver tous les intervalles de I qui passent par-dessus un point x donné en temps k + log(log(U)) au lieu de k + log(n) si k est le nombre de réponses, grâce à la structure d'arbre de recherche avec priorité.

Quelques autres problèmes importants[modifier | modifier le code]

Difficultés et techniques[modifier | modifier le code]

Une difficultée est le fléau de la dimension : les algorithmes classiques deviennent inutilisable si les données appartiennent à un espace de grande dimension. Une technique classique est d'utiliser des algorithmes probabilistes[2].

Notes et références[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Introduction à la modélisation et à l'algorithmique géométrique