Abstract FR:

Une methode generale est presentee pour determiner l'enveloppe convexe d'un ensemble fini de points dans r#d. Pour definir la structure faciale d'un d-polytope, un nouveau graphe, dit de connexion, est introduit; il permet d'eviter les tris effectues pour la mise a jour des relations d'adjacence a chaque etape d'insertion de point; en ce sens cette methode fournit un automate pour la resolution du probleme. Cette methode est appliquee a une construction de l'i-dag propose par boissonnat et al. Les deux algorithmes sont de complexite optimale, en temps d'execution, dans leur version randomisee. Nous appliquons le concept de graphe de connexion au probleme de la triangulation d'un nuage de points, simple et de delaunay. Ce graphe nous libere de l'obligation usuelle d'inclure le nuage de points dans un ou plusieurs simplexes englobants pour ne traiter que des points internes a la triangulation. Les cas degeneres sont aussi traites. Nous proposons un algorithme dynamique pour resoudre le probleme de la triangulation de delaunay sous contraintes dans r#2; cet algorithme realise l'insertion et la suppression de points et d'aretes; il utilise les proprietes de convexite des triangulations; il presente l'avantage d'etre recursif. L'algorithme introduit est adapte a la resolution des problemes d'evolution, ou les points et les aretes contraintes peuvent etre deplaces. Une extension a r#3 est basee sur l'ajout de points dans les faces contraintes. Une implementation en pascal a permis de verifier l'efficacite de notre methode pour resoudre des problemes de contraintes poses dans r#2 et r#3