Identifiant pérenne de la notice : 211367672
Notice de type
Notice de regroupement
Note publique d'information : 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.