Abstract FR:

La résolution de certains problèmes de Mathématiques Appliquées et d'Informatique nécessite la construction du partitionnement d'un espace euclidien (dimension d) par des familles d'hyper-surfaces (dimension d-1). La complexité d'un tel outil, faisant intervenir des techniques d'analyse numérique et d'algorithmique, dépend de la dimension choisie ainsi que de la nature des hyper-surfaces traitées. La méthode classiquement utilisée pour construire effectivement de tels arrangements fait appel à l'algorithme incrémental dit «de suivi d'intersection». Dans cette thèse, nous étudions d'un point de vue théorique et pratique le partitionnement de l'espace 2D par des courbes paramétrées ou implicites: des résultats de complexité et un choix de structure de données adaptée accompagnent l'exposé des algorithmes proposés. A titre d'application, nous proposons différentes méthodes permettant de résoudre le problème de la détermination du graphe d'aspects d'un polyèdre convexe, problème 3D rencontré en particulier dans le domaine de la Vision par Ordinateur. Nous montrons que la technique de suivi d'interaction peut être adaptée au cas du partitionnement de l'espace 3D des plans