Discussion:Géométrie algorithmique
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Revision et enveloppe convexe[modifier le code]
L'article devrait sans doute être revu. Si l'on prend par exemple le calcul d'enveloppe convexe d'un ensemble de points en 2D, le parcours de Graham (Graham scan) n'est pas l'algorithme qui a la meilleure complexité dans le pire cas. Si l'on introduit le nombre h d'arêtes de l'enveloppe convexe calculée, les algorithmes "mariage before conquest" (Kirkpatrick, Seidel 1986) et l'algorithme de Chan (1995) sont en n log(h) -au lieu de n log n pour Graham scan. Cette complexité dans le pire cas est optimale (on ne peut pas fournir un algorithme d'enveloppe convexe avec une complexité dans le pire cas inférieure - D. G. Kirkpatrick and R. Seidel, ``The ultimate planar convex hull algorithm, SIAM J. Comput., 15, 1986, 287--299. La question est donc loin d'être ouverte comme semble le dire l'article.
A tout cela, il faudrait sans doute ajouter d'autres problèmes de géométrie algorithmique qui font la richesse de ce domaine (entre autres, les problèmes de calcul de triangulations -Delaunay, Delaunay contraint- ou de diagramme de Voronoï) et telles qu'il en fait mention sur la page anglaise, plus complète sur le sujet, "computational geometry" de wikipedia.
M.