Algorithmes géométriques,théorie et pratique

Ce cours traite de la géométrie algorithmique par la triangulation de Delaunay et les diagrammes de Voronoï.  Ce cours est accompagné d'une démonstration des fonctionnalités de CGAL. Le but de ce module  est de présenter les grandes tendances de la  géométrie algorithmique actuelle,et en particulier son évolution vers ce que nous appellerons le  calcul géométrique. Après plusieurs années où la géométrie algorithmique a connu des développements plutôt théoriques,une des grandes questions actuelles est : Comment passer à des algorithmes effectivement programmés ?  On explorera les principaux problèmes de la géométrie et leurs solutions. On regardera les algorithmes classiques (théoriques) mais aussi les problèmes plus pratiques posés par les incertitudes numériques ou la complication excessive de ces algorithmes classiques. On utilisera la bibliothèque CGAL (www.cgal.org) pour passer à la pratique. Les domaines d'applications sont extrêmement variés allant de la modélisation des sites archéologiques au placement d'antennes dans un réseau de téléphonie mobile en passant par la simulation d'écoulement de fluides.

Mots-clés : algorithme géométrique,triangulation de Delaunay,diagramme de Voronoï,relation d'Euler,algorithme incrémental,probablilités,CGAL,Computational Geometry Algorithms Library,2D,3D,maillage,fuscia
Type de document : texte,image,logiciel
Type de ressource : lecture,démonstration
Niveau : higher education,master,bac+5
Publics visés : learner,teacher
Activité induite : apprendre,se former
Proposition d'utilisation : Les prérequis de ce cours sont des connaissances en algorithmique : algorithmes de tri (tri fusion, quick sort), les arbres binaires équilibrés et la connaissance du langage C++.
Auteurs ou éditeurs : Pierre Alliez,Monique Teillaud,Olivier Devillers,Université de Nice