Alain Daurat
Thèse de Doctorat de l'Université Paris 7
Date de soutenance : 11 décembre 2000
Lieu : IUT Informatique Clermont-Ferrand
Numéro CNRS/CCSD : tel-00012136
Titre de la thèse : Convexité dans le plan discret. Application à la tomographie.
La première partie de cette thèse est consacrée à l'étude des convexes dans le plan discret ℤ2 ou plus généralement ℤn. Il existe en fait plusieurs notions de convexité discrète : la convexité simple selon certaines directions, la convexité totale (la convexité usuelle du continu), etc. La Q-convexité est encore une nouvelle classe qui généralise à la fois les totalement convexes et les polyominos HV-convexes. On étudie les liens entre toutes ces différentes notions, et on donne des propriétés des points particuliers de ces ensembles comme les points médians et les points saillants.
Toute la deuxième partie est dédiée au problème de la tomographie dans le plan discret ℤ2. Il s'agit simplement de reconstruire un ensemble à partir du nombre de points dans les droites parallèles à des directions données. L'algorithme polynomial, déjà connu pour les polyominos HV-convexes avec les directions horizontales et verticales, se généralise aux Q-convexes pour des directions quelconques. D'autre part, le théorème d'unicité qui montre en particulier que sept directions suffisent pour déterminer un totalement convexe se généralise aussi aux Q-convexes. On en déduit que lorsque l'on a assez de directions pour avoir unicité de la solution, la reconstruction des totalement convexes peut se faire en temps polynomial. On a aussi un algorithme polynomial de reconstruction approchée des Q-convexes.
Jury
Gilles Bertrand, rapporteur
Alberto Del Lungo
Attila Kuba, rapporteur
Jacques Mazoyer, président du jury
Maurice Nivat, directeur
Jean-Pierre Reveillès, rapporteur
Denis Richard
| Texte intégral : | PS.Z | PS.GZ |