Géométrie algorithmique

Géométrie algorithmique

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.

Sommaire

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))\,. Le fait de savoir s'il existe un meilleur algorithme reste un problème ouvert, 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.

Dans le cas de d'une dimension quelconque d (d > 3) les meilleurs algorithmes connus sont en O(n^{\lfloor{\frac{d}{2}}\rfloor+1}).

Problèmes d'algorithmique générale

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]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é. La 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 \sqrt{\log(U)} au lieu de log(n) grâce à la structure de q-fast-trie.
  • Étant donnée 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

Liens externes

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Géométrie algorithmique de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Geometrie algorithmique — Géométrie algorithmique 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 …   Wikipédia en Français

  • Géométrie Algorithmique — 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… …   Wikipédia en Français

  • ALGORITHMIQUE — L’objet de l’algorithmique est la conception, l’évaluation et l’optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d’un schéma de calcul, sous forme d’une suite d’opérations… …   Encyclopédie Universelle

  • Algorithmique — Organigramme de programmation représentant l algorithme d Euclide L algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d algorithmes, c est à dire de processus systématiques de… …   Wikipédia en Français

  • Geometrie euclidienne — Géométrie euclidienne Euclide. La géométrie euclidienne commence avec les Éléments d Euclide, qui est à la fois une somme des connaissances géométriques de l époque et une tentative de formalisation mathématique de ces connaissances. Les notions… …   Wikipédia en Français

  • Géométrie Euclidienne — Euclide. La géométrie euclidienne commence avec les Éléments d Euclide, qui est à la fois une somme des connaissances géométriques de l époque et une tentative de formalisation mathématique de ces connaissances. Les notions de droite, de plan, de …   Wikipédia en Français

  • Géométrie plane — Géométrie euclidienne Euclide. La géométrie euclidienne commence avec les Éléments d Euclide, qui est à la fois une somme des connaissances géométriques de l époque et une tentative de formalisation mathématique de ces connaissances. Les notions… …   Wikipédia en Français

  • Géométrie euclidienne — Euclide. La géométrie euclidienne commence avec les Éléments d Euclide, qui est à la fois une somme des connaissances géométriques de l époque et une tentative de formalisation mathématique de ces connaissances. Les notions de droite, de plan, de …   Wikipédia en Français

  • Complexite algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexité Algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”