Géométrie algorithmique

L'objet du calcul géométrique est de représenter, calculer et manipuler les objets géométriques. Le calcul géométrique remonte aux origines des mathématiques et a été développé avec des points de vue très différents selon les époques et les cultures, pratique chez les arpenteurs égyptiens qui évaluaient des aires et des volumes, plus abstrait chez les grecs avec les constructions à la règle et au compas. Les premiers se souciaient principalement de calculs numériques et connaissaient des approximations assez précises de Pi. Les seconds inventaient une démarche algorithmique sans se préoccuper de la précision de leurs tracés. Ces deux points de vue se retrouvent aujourd'hui alors que l'ordinateur a renouvelé le calcul géométrique et lui donne un rôle clé dans de nombreuses applications.

Les premiers objets géométriques qui ont été créés et manipulés sur un ordinateur étaient des objets manufacturés, à la géométrie complexe mais à la construction relativement simple : on pouvait les dessiner sur un écran d'ordinateur avec un système de CAO.

L'intérêt pour les questions combinatoires est apparu plus récemment quand il a fallu représenter des objets de grandes tailles : objets naturels (organes, molécules, surfaces géologiques), scènes complexes comportant des millions de facettes des mondes réels ou virtuels de l'infographie, objets plongés dans des espaces de grandes dimensions comme les espaces de configuration de robots.

Naissance de la géométrie algorithmique
Le calcul géométrique a ainsi évolué et l'étude traditionnelle des courbes et des surfaces s'est vue complétée par l'analyse des aspects algorithmiques. La géométrie algorithmique est ainsi devenue à la fin des années 70 une nouvelle branche de l'informatique qui étudie la conception et l'analyse des algorithmes géométriques : calcul d'intersections, problèmes de visibilité, planification de trajectoires, optimisation géométrique etc. La résolution de ces problèmes s'appuie souvent sur la construction d'un petit nombre de structures de données géométriques fondamentales : arbres de recherche multidimensionnelle, triangulations, cartes, polyèdres, arrangements, diagrammes de Voronoï.
Source