Abstract FR:

La premiere partie de cette these est consacree a l'etude des convexes dans le plan discret z2 ou plus generalement zn. Il existe en fait plusieurs notions de convexite discrete : la convexite simple selon certaines directions, la convexite totale (la convexite usuelle du continu), etc. La q-convexite est encore un nouvelle classe qui generalise a la fois les totalement convexes et les polyominos hv-convexes. On etudie les liens entre toutes ces differentes notions, et on donne des proprietes des points particuliers de ces ensembles comme les points medians et les points saillants. Toute la deuxieme partie est consacree au probleme de la tomographie dans le plan discret z2. Il s'agit simplement de reconstruire un ensemble a partir du nombre de points dans les droites paralleles a des directions donnees. L'algorithme polynomial deja connu pour les polyominos hv-convexes avec les directions horizontales et verticales se generalise aux q-convexes pour des directions quelconques. D'autre part le theoreme d'unicite qui montre en particulier que 7 directions suffisent pour determiner un totalement convexe se generalise aussi aux q-convexes. On en deduit que lorsque l'on a assez de directions pour avoir unicite de la solution la reconstruction des totalement convexes peut se faire en temps polynomial. D'autre part on a aussi pour les q-convexes un algorithme polynomial de reconstruction approchee.