Géométrie algorithmique

vignette|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 géométrie algorithmique est l'étude des algorithmes manipulant des objets géométriques. Par exemple, le problème algorithmique qui consiste, étant donné un ensemble de points dans le plan décrits par leurs coordonnées, à trouver la paire de points dont la distance est minimale est un problème d'algorithmique géométrique. 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 maquettes dans la conception d'objets, à partir des années 1970. Ces modèles permettent ensuite l'étude d'une grande diversité de phénomène du monde réel. 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 infographie, en robotique, pour les systèmes d'information géographique, et la conception par ordinateur. Certaines structures pouvant être utilisées à l'entrée du problème ou à l'intérieur de l'algorithme sont centrales en géométrie algorithmique : les polyèdres, les diagrammes de Voronoï, et les triangulations. 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.