La première partie de cette thèse est consacrée à l'étude des convexes dans le plan discret Z2 ou plus généralement Zn. 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.<br /><br />Toute la deuxième partie est dédiée au problème de la tomographie dans le plan discret Z2. 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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00012136 |
| Date | 11 December 2000 |
| Creators | Daurat, Alain |
| Publisher | Université Paris-Diderot - Paris VII |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0023 seconds