Daurat
Le Jeudi 15 Février 2001 à 14h30
(LLAIC, IUT Clermont-Ferrand)
Tomographie discrète et Q-convexité
Résumé/Abstract :
Le problème de la reconstruction en tomographie discrète
consiste à retrouver une partie du plan discret à partir
du nombre de points sur chaque droite parallèle à certaines
directions (les projections).
En 1996 Barcucci et al. ont trouvé un algorithme en temps polynomial
résolvant ce problème pour les polyominos HV-convexes
(appelés polyominos convexes en combinatoire) et les directions
horizontales et verticales, en revanche dans beaucoup de cas il n'y a pas
unicité de la solution reconstruite. Auparavant Gardner et Gritzmann
avaient montré qu'on avait unicité dans le cas des convexes
usuels dès que l'on se donne plus de 7 directions, mais sans avoir
d'algorithme polynomial de reconstruction.
Or on peut définir une notion intermédiaire entre les
polynominos HV-convexes et les convexes usuels : la Q-convexité.
Cette notion dépend d'un ensemble de directions. Les deux
résultats précédents s'étendent à cette
nouvelle notion. Ceci résout (partiellement) un problème
posé par Gritzmann : on peut reconstruire en temps polynomial
les convexes usuels pour les ensembles de directions pour lesquels il y
a unicité.