Nouvelle Approche Efficace pour la Reconnaissance de Plans Discrets 

Télécharger le fichier pdf d’un mémoire de fin d’études

Fractions Continues

D`es le Moyen Age, des math´ematiciens indiens utilisaient les fractions continues. Elles apparaissent ensuite en Europe au XVIIe si`ecle et sont encore de nos jours largement etudi´ees. Nous introduisons dans cette section la d´efinition des fractions continues ainsi que diff´erentes propri´et´es interpr´et´ees du point de vue num´erique et du point de vue g´eom´etrique.
Une introduction aux fractions continues plus d´etaill´ee est disponible dans [Chr89] ou [Dav92]. D´efinition 3 La fraction continue simple d’un nombre r´eel x correspond `a : 1 x = a0 + a1 + a2+ 1 1 1a3+ o`u a0 repr´esente une valeur enti`ere et o`u chaque ai repr´esente une valeur positive enti`ere pour i ≥ 1. Habituellement, nous utilisons la notation x = [a0, a1, a2, ] et le terme ai est appel´ le coefficient d’indice i de la fraction continue.
Le calcul de la d´ecomposition en fraction continue d’un rationnel a/b se fait en ex´ecu-tant l’algorithme d’Euclide ´etendu introduit dans la section 1.2.1 avec a et b en param`etres [FV98]. En effet, les quotients de la s´erie Q = (q2, , qn−1) g´en´er´ee lors du d´eroulement de l’algorithme correspondent aux coefficients de la fraction continue.
D´efinition 4 Les convergents principaux d’un nombre r´eel x correspondent a` leurs ap-proximations rationnelles pk /qk . Ils sont obtenus en tronquant la d´ecomposition en frac-tions continues de x apr`es le coefficient d’indice k. Le num´erateur et le d´enominateur des convergents principaux sont calcul´es de la mani`ere suivante :
p0 = a0 p1 = a0a1 + 1 pk+2 = pk + ak+2pk+1.
q0 = 1 q1 = a1 qk+2 = qk + ak+2qk+1.
Chaque convergent d’indice pair est plus petit que le r´eel x et chaque convergent d’indice impair est plus grand que le r´eel x. La valeur de chaque convergent est plus proche de x que le convergent pr´ec´edent.
D´efinition 5 Les convergents interm´ediaires entre deux convergents principaux pk /qk et pk+2/qk+2 sont d´efinis de la mani`ere suivante : pk + ipk+1 , i = 1 ak − 1 qk + iqk+1.
Notons SP et SI les suites d´efinies respectivement par tous les convergents principaux d’indice pair et d’indice impair, intercal´es avec leurs convergents interm´ediaires. Nous ajoutons respectivement les fractions 0/1 et 1/0 au d´ebut de chacunes des suites SP et SI si elles ne commencent pas d´ej`a par ces fractions. Lorsque x est un nombre rationnel, alors une de ces deux suites ne se termine pas par x. Dans ce cas, nous ajoutons le nombre rationnel x `a la fin de cette suite. Nous utilisons les notations suivantes : [SP1 , SP2 , ] correspond `a la suite SP et [SI1 , SI2 , ] correspond `a la suite SI . Nous remarquons que la suite SP (resp. SI ) est strictement croissante (resp. strictement d´ecroissante) et que la suite des d´enominateurs de SP et de SI est croissante.
Une autre fa¸con de visualiser le d´eveloppement en fractions continues d’un nombre ra-tionnel consiste `a utiliser l’arbre de Stern-Brocot (voir [GKP94]). L’arbre de Stern-Brocot a et´ d´ecouvert il y a plus de 150 ans simultan´ement par un math´ematicien allemand nomm´e Moritz Stern et par un horloger fran¸cais r´epondant au nom d’Achille Brocot. L’arbre de Stern-Brocot est une repr´esentation de toute les fractions irr´eductibles posi-tives. Pour le construire, nous pouvons imaginer que nous ´ecrivons respectivement les fractions 0/1 et 1/0 `a l’extrˆeme gauche et `a l’extrˆeme droite. Ensuite, nous intercalons entre deux fractions leur fraction m´ediante de fa¸con `a construire un arbre de racine 1/1. La fraction m´ediante de deux fraction a/b et c/d correspond `a la fraction (a + c)/(b + d). Pour retrouver une fraction dans l’arbre de Stern-Brocot, nous utilisons son d´eveloppe-ment en fraction continue qui d´etermine le chemin `a parcourir depuis la racine de l’arbre pour atteindre la fraction. Soit [a0, a1, , am] le d´eveloppement en fraction continue d’un rationnel x. Les coefficients d’indice pair indiquent un nombre de d´eplacements vers la droite dans l’arbre de Stern-Brocot. Les coefficients d’indice impair indiquent un nombre de d´eplacements vers la gauche dans ce mˆeme arbre. Une exception pour le dernier coeffi-cient am auquel il faut retrancher 1 pour obtenir un nombre de d´eplacements. Consid´erons par exemple le rationnel x = 7/4 de d´eveloppement en fraction continue [1, 1, 3]. Pour le retrouver dans l’arbre de Stern-Brocot `a partir de la racine, il faut donc effectuer un d´e-placement vers la droite, puis un d´eplacement vers la gauche et enfin deux d´eplacements vers la droite (voir la figure 1.10). Ces d´eplacements dans l’arbre de Stern-Brocot peuvent ´egalement ˆetre vus de fa¸con matricielle. Soit p/q une fraction dans l’arbre de Stern-Brocot. Cette fraction peut ˆetre repr´esent´ee comme le vecteur (p, q)T . Nous obtenons la fraction situ´ee a` gauche de p/q dans l’arbre de Stern-Brocot en multipliant le vecteur (p, q)T par la matrice de transvection verticale de coefficient 1. De la mˆeme mani`ere, nous obtenons la fraction situ´ee `a droite de p/q dans l’arbre de Stern-Brocot en multipliant le vecteur (p, q)T par la matrice de transvection horizontale de coefficient 1. Ainsi, soit [a0, a1, , am] le d´eveloppement en fraction continue d’un rationnel x = r/s, nous v´erifions que :
1 a0 1 0 1 a2 1 = r
0 1 a1 1 0 1 1 s
Nous ´enon¸cons une proposition qui sera d´eterminante par la suite pour r´esoudre le probl`eme d’approximation du Chapitre 2 (voir [Chr89] pour la preuve) :
Proposition 2 Soit r le nombre rationnel plus petit (resp. plus grand) qu’un nombre r´eel a, qui approxime au mieux a et tel que son d´enominateur n’exc`ede pas un entier donn´e d. Le nombre rationnel r est le terme de la suite SP (resp. SI ) de a de plus grand d´enominateur n’exc´edant pas d.

Le polytope du Probl`eme du Sac a` Dos

Le probl`eme du sac `a dos, ´egalement connu sous le nom de knapsack problem, est un probl`eme bien connu de programmation lin´eaire en nombres entiers, propos´e pour la premi`ere fois par Mathews dans [Mat97]. Il s’agit de remplir un sac `a dos avec des objets dont nous connaissons le poids et la valeur. Le sac `a dos ne pouvant supporter plus d’un certain poids, il convient donc de faire les bons choix afin de maximiser la valeur totale du sac `a dos sans d´epasser le poids maximum. Evidemment, les objets ne peuvent pas ˆetre “coup´es en deux” mais nous pouvons prendre plusieurs exemplaires d’un mˆeme objet. Nous nous retrouvons alors clairement avec un probl`eme de programmation lin´eaire en nombres entiers qui peut ˆetre formalis´e de la mani`ere suivante : maximiser c1x1 + c2x2 + + cdxd sous la contrainte a1x1 + a2x2 + + adxd ≤ b (1.2).
o`u a et c correspondent `a des vecteurs de (Z+)d et b correspond a` un entier positif. Dans cette formulation, l’entier b correspond au poids total pouvant ˆetre support´e par le sac `a dos. De plus, a` chaque objet i, 1 ≤ i ≤ d, est associ´e une valeur ci repr´esentant l’importance accord´ee `a cet objet, un poids ai et enfin une quantit´e xi. Nous appelons 7×1 + 4×2 = 36 x2 x1 solution r´ealisable du probl`eme du sac a` dos tout point de (Z+)d satisfaisant l’in´equation de (1.2). Le polytope du probl`eme du sac a` dos (knapsack polytope), not´e K, correspond `a l’enveloppe convexe de l’ensemble des solutions r´ealisables du probl`eme du sac `a dos et s’´ecrit : K = conv{x = (x1, , xd) ∈ (Z+)d : a1x1 + a2x2 + + adxd ≤ b}.
Parmi les solutions r´ealisables, la solution optimale maximisant la valeur totale du sac `a dos c1x1 + c2x2 + + cdxd est recherch´ee. Il est prouv´e qu’elle est toujours atteinte pour un sommet du polytope du probl`eme du sac `a dos ([Ste01, Zol00]). En dimension 2, nous consid`erons que nous ne disposons que de deux types d’objets `a mettre dans le sac `a dos. Le polytope du probl`eme du sac `a dos correspond alors `a un polygone convexe `a sommets port´es par la grille comme sur l’exemple de la figure 1.25. Tout point entier de coordonn´ees (x, y) inclus dans ce polygone repr´esente la possiblit´e de remplir le sac `a dos avec x objets du premier type et y objets du second type, sans d´epasser le poids maximum autoris´e.
Soit V l’ensemble des sommets du polytope du probl`eme du sac `a dos. Le cardinal de V s’av`ere relativement petit et plusieurs ´etudes cherchent a` borner cette quantit´e. Soit γ = min{a1, , ad}, Hayes et al. montrent dans [HL83] qu’il admet une borne sup´erieure et que : |V | < (log2((4b)/γ))d) (1.3)
C’est en 2000 que Zolotykh am´eliore cette borne et prouve dans [Zol00] que : |V | ≤ d log(2d)(1 + log(1 + b/γ))d−1 (1.4)
D’apr`es ce dernier r´esultat, nous pouvons conclure que lorsque la dimension d est fix´ee, le cardinal de V est born´e par O(log(b/γ)d−1). Dans le chapitre suivant, nous mettons en place un algorithme calculant l’enveloppe convexe des points entiers de la grille bordant une droite et situ´es dans un domaine vertical born´e. Le r´esultat de Zolotykh nous sera alors utile afin de borner le nombre de sommets de l’enveloppe convexe `a calculer.

Droite Approxim´ee et Enveloppe Convexe En-ti`ere

Soit a un nombre r´eel positif et soit L une droite d’´equation y = ax. Nous supposons sans perte de g´en´eralit´ que a est inf´erieur `a 1. Soient b et b′ deux nombres entiers positifs tels que b est inf´erieur `a b′. Soit D le domaine vertical de la forme {(x, y) ∈ R 2 |b ≤ x ≤ b′ }. Dans la partie g´eom´etrique de ce chapitre, nous parlons souvent de points `a coordonn´ees enti`eres. Dans un souci de clart´e, nous utilisons donc le terme “point entier” plutˆot que le terme “point `a coordonn´ees enti`eres”. De la mˆeme mani`ere, nous utilisons le terme “enve-loppe convexe enti`ere” pour d´ecrire l’enveloppe convexe d’un ensemble de points entiers, les sommets d’une telle enveloppe ´etant eux-mˆeme entiers.
Nous nous int´eressons au probl`eme de d´etermination du nombre rationnel p/q qui ap-proxime au mieux le nombre r´eel a tel que son d´enominateur q appartienne `a l’intervalle born´e [b, b′]. Nous ´etablissons une correspondance entre le nombre rationnel p/q et le point en-tier (q, p) dans le plan euclidien. En effet, toute droite de pente rationnelle d’´equation
y = (p/q)x passe par le point entier (q, p). Par cons´equent, le probl`eme de l’approxi-mation par un rationnel est ´equivalent, dans le plan euclidien, `a trouver le point entier P = (q, p) appartenant au domaine D tel que la droite passant par l’origine et par le point P approxime au mieux la droite d’´equation y = ax par rapport au domaine D. Ce point
P = (q, p) est appel´ meilleur point approximant la droite L par rapport au domaine D lorsque P v´erifie les conditions suivantes : P appartient au domaine D et la valeur absolue de l’angle entre les deux droites de la forme y = ax et y = (p/q)x est minimal. Ceci implique qu’aucun point entier du domaine D ne se situe entre ces deux droites.
Le probl`eme d’approximation dans le plan euclidien est li´e au calcul d’enveloppes convexes enti`eres. Notons CHU et CHL les enveloppes convexes des points entiers du domaine D situ´es respectivement au-dessus et en dessous de la droite L (voir la figure 2.1). De toute ´evidence, le meilleur point approximant P que nous cherchons a` d´eterminer correspond a` un des sommets de CHU ou de CHL. En effet, quel que soit le point entier (r, s) dans le domaine D n’appartenant pas aux enveloppes convexes, il existe un sommet de CHU ou de CHL situ´e entre les deux droites d’´equations y = ax et y = (s/r)x. Notons h le nombre de sommets des enveloppes convexes CHU et CHL. D’apr`es [Zol00], r´esultat pr´esent´ en section 1.4.2, nous savons que h est logarithmique en la largeur du domaine D, i.e. CHU et CHL comportent O(log(b′ −b)) sommets. Ainsi, si nous avons calcul´e ces deux enveloppes convexes, nous pouvons r´esoudre le probl`eme d’approximation en O(h). Pour calculer ces deux enveloppes convexes, nous pourrions consid´erer les (b′ − b) + 1 points entiers situ´es juste au-dessus de la droite L et les (b′ − b) + 1 points entiers situ´es juste en dessous de la droite L, `a savoir les droites discr`etes de L. Puis, nous pourrions utiliser un des algorithmes g´en´eraux de calcul d’enveloppes convexes existants (voir la section 1.3.2). Un des plus c´el`ebres s’appelle l’algorithme du gift wrapping et sa complexit´ en temps est de l’ordre de O((b′ − b)h). Cependant, nous pr´ef`ererions utiliser la m´ethode propos´ee par Chan en 1996 qui atteint une complexit´ en O((b′ − b) log h) ce qui est optimal dans le cas g´en´eral, i.e. en consid´erant un nuage de points (voir [Jar73] et [Cha96]). Cependant, comme les points entiers qui nous int´eressent sont les points d’une grille r´eguli`ere situ´es au-dessus et en dessous d’un segment de droite, nous pouvons appliquer des algorithmes beaucoup plus sp´ecifiques pour calculer les enveloppes convexes. Nous commen¸cons par introduire deux approches existantes, l’une utilise la th´eorie des nombres et l’autre met en oeuvre des techniques de g´eom´etrie algorithmique. Ces algorithmes atteignent respectivement des complexit´es en temps de O(log b′) et de O(log(b′ − b)), ce qui est bien meilleur que la complexit´ des approches dites g´en´erales.

R´esoudre un Sous-Probl`eme avec les Fractions Continues

Dans cette section, le sous-probl`eme qui nous int´eresse est le suivant : d´eterminer le nombre rationnel p/q qui approxime au mieux le nombre r´eel a et tel que q n’exc`ede pas la valeur enti`ere b′. Nous montrons comment r´esoudre ce probl`eme num´eriquement et g´eom´etriquement en utilisant les fractions continues.
Nous remarquons que le sous-probl`eme de cette section peut facilement ˆetre r´esolu en calculant les deux suites SP et SI issues du d´eveloppement en fraction continue de a (voir section 1.2.2). D’apr`es la proposition 2, nous savons que le dernier terme de la suite SP (resp. SI ) dont le d´enominateur ne d´epasse pas b′ correspond a` la meilleure approximation rationnelle de a inf´erieure (resp. sup´erieure) `a a. Nous illustrons cette proposition avec l’exemple 2).
Exemple 2 Nous souhaitons d´eterminer le nombre rationnel dont le d´enominateur n’ex-c´ede pas 80 et qui approxime au mieux le rationnel 779/207. Nous avons le d´eveloppement en fraction continue suivant : 779/207 = [3, 1, 3, 4, 2, 5]. Nous pouvons ainsi calculer les deux suites :
SP = 01 , 11 , 21 , 31 , 72 , 113 , 154 , 7921 , 14338 , 779207
SI = 10 , 41 , 195 , 349 , 4913 , 6417 , 20755 , 35093 , 493131 , 636169 , 779207
De ces suites, nous d´eduisons que le rationnel 143/38 de la suite SP (resp. le rationnel 207/55 de la suite SI ) correspond `a la meilleure approximation de 779/207 inf´erieure (resp. sup´erieure) `a 779/207, dont le d´enominateur ne d´epasse pas 80. A partir de ces deux fractions, nous en d´eduisons que le nombre rationnel 143/38 correspond `a la meilleure approximation de 779/207 telle que son d´enominateur ne d´epasse pas 80.
Dans le plan euclidien, ce sous-probl`eme est ´equivalent a` d´eterminer le point entier (q, p) qui approxime au mieux la droite d’´equation y = ax tel que son abscisse n’ex-c`ede pas b′. Nous pouvons interpr´eter g´eom´etriquement la fraction continue associ´ee `a un nombre r´eel a en faisant correspondre les nombres rationnels avec des points entiers P Q d=6(11,4) et ainsi interpr´eter la Proposition 2 comme la Proposition 3 dans le plan euclidien (voir la section 1.2.2). Le meilleur point approximant que nous cherchons correspond donc au dernier terme de la s´erie KL ou de la s´erie KU dont l’abscisse n’exc`ede pas b′. La figure 2.2 montre un exemple de suites de points entiers KL et KU pour a = 4/11. Dans cet exemple, les points entiers P = (5, 2) et Q = (3, 1) correspondent aux points approximant au mieux la droite de pente 4/11 tels que leur abscisse ne d´epasse pas 6.

R´esoudre le Probl`eme d’Approximation avec les Fractions Continues

A partir de maintenant, nous nous int´eressons `a un probl`eme plus contraint. Nous souhaitons d´eterminer le nombre rationnel p/q qui approxime au mieux le nombre r´eel a et tel que son d´enominateur q appartient a` l’intervalle born´e [b, b′]. En r´ealit´e, nous traitons la version g´eom´etrique de ce probl`eme : d´eterminer le point entier (q, p) du domaine D = {(x, y) ∈ R2|b ≤ x ≤ b′} qui approxime au mieux la droite L d’´equation y = ax.

Description de l’Algorithme

Pour r´esoudre ce probl`eme, nous pouvons toujours utiliser les fractions continues et l’interpr´etation g´eom´etrique de la proposition 2 `a la mani`ere d’Harvey dans [Har99]. Pour cela, nous calculons la voile de Klein sup´erieure et inf´erieure de la droite L. Puis, nous s´e-lectionnons le point entier de plus grande abscisse appartenant au domaine D sur chaque voile de Klein et nous les comparons. Malheureusement, il est possible qu’aucun point entier port´e par les voiles de Klein ne se situe dans le domaine D. Soit t l’indice du point entier de la suite KL ou de la suite KU d’abscisse maximale mais toutefois inf´erieure `a b′. Supposons qu’il s’agit d’un point de KL et notons ce point KLt . Si le point KLt ou un point de la forme αKLt avec α ∈ N appartient au domaine D, d’apr`es la proposition 3, il correspond forc´ement au meilleur point approximant que nous recherchons et l’algorithme se termine. Dans le cas contraire, l’algorithme r´eit`ere. Pour cela, nous translatons l’ori-gine du rep`ere au point entier βKLt o`u β est une valeur enti`ere positive telle que βKLt corresponde au point le plus proche de la droite d’´equation x = b, a` gauche du domaine D. Nous r´eit´erons avec la droite L′ de vecteur directeur KLt et avec le domaine D′ de la forme {(x, y) ∈ R2|b−βxLt ≤ x ≤ b′−βxLt } o`u xLt correspond `a l’abscisse du point KLt .
Nous pouvons remarquer que, lorque nous r´eit´erons, aucun point entier du domaine D ne se situe entre les droites L et L′ (voir Proposition 3). Par cons´equent, nous ne manquons aucun point entier susceptible de correspondre au meilleur point approximant recherch´. De plus, le calcul de la voile de Klein lors des it´erations suivantes se fait en temps constant. En effet, les points entiers port´es par cette voile correspondent exactement au t-i`eme premiers termes de la voile de Klein `a l’it´eration pr´ec´edente.

Exemple de D´eroulement et Discussion sur l’Algorithme

Un court exemple du d´eroulement de l’algorithme est illustr´e par la figure 2.3. Dans cet exemple, nous consid´erons la droite L d’´equation y = (11/14)x ainsi que le domaine D de la forme {(x, y) ∈ R2|10 ≤ x ≤ 13}. La voile de Klein inf´erieure de L correspond `a la suite de points entiers [(1, 0), (2, 1), (3, 2), (4, 3), (9, 7), (14, 11)] et elle est illustr´ee en figure 2.3.a. Comme aucun terme de cette s´erie ne correspond a` une solution du pro-bl`eme d’approximation, nous r´eit´erons l’algorithme. Nous translatons l’origine du rep`ere au point KL5 = (9, 7). Dans ce nouveau rep`ere, nous consid´erons le nouveau domaine D′ d´efini par {(x, y) ∈ R2 |1 ≤ x ≤ 4} ainsi que la droite L′ de vecteur directeur (9, 7) comme sur la figure 2.3.b. La voile de Klein inf´erieure associ´ee `a la nouvelle droite L′ correspond `a la suite de points [(1, 0), (2, 1), (3, 2), (4, 3), (9, 7)]. Les quatre premiers points de cette suite appartiennent au domaine D′, donc le point P = KL′4 = (4, 3) est solution de notre probl`eme d’approximation. Par cons´equent, dans le rep`re initial, le meilleur point ap-proximant la droite L de pente 11/14 d’abcisse `a la fois sup´erieure `a 10 et inf´erieure `a 13 correspond au point (13, 10).
La m´ethode de Harvey n´ecessite la connaissance d’un point `a coordonn´ees enti`eres port´e par la droite `a approximer, point consid´er´ comme origine du rep`ere. Son algorithme doit alors calculer dans le pire cas O(log(b′)) convergents de la pente de la droite L. Notons que la th´eorie des nombres et en particulier les fractions continues peuvent probablement r´esoudre le probl`eme d’approximation pour des droites ne passant pas par l’origine [AB98]. En effet, en utilisant le syst`eme de num´eration d’Ostrowski [Ost22] a` la mani`ere de Berth´ et Imbert dans [BI09], nous voyons que l’intercept de la droite L (c’est-`a-dire l’ordonn´ee de son intersection avec l’axe des y) peut ˆetre exprim´ee en fonction du d´eveloppement en fractions continues de la pente de la droite L. Il existe ainsi peut ˆetre un moyen d’approximer des droites ne passant pas par l’origine du rep`re en utilisant des outils de la th´eorie des nombres.
Nous remarquons que la valeur b′ peut ˆetre beaucoup plus grande que la valeur (b′ −b) qui correspond `a la largeur du domaine vertical. Dans ce cas, nous devons am´eliorer la complexit´ en temps pour le calcul de la meilleure approximation. En effet, nous souhaitons r´esoudre ce probl`eme en O(log(b′ − b)) dans le pire cas. Bien que des outils de la th´eorie des nombres puisse peut ˆetre mener `a cette complexit´ optimale, ils peuvent s’av´erer assez complexes `a utiliser dans ce cas. Nous introduisons donc une seconde approche utilisant la g´eom´etrie algorithmique.

Une Seconde Approche Utilisant la G´eom´etrie Algorithmique

Les notations ⌊x⌋ et ⌈x⌉ repr´esentent respectivement les valeurs enti`eres inf´erieures et sup´erieures du nombre r´eel x. Nous rappelons que la valeur enti`ere inf´erieure de x corres-pond au plus grand nombre entier plus petit que x. De la mˆeme mani`ere, la valeur enti`ere sup´erieure de x correspond au plus petit nombre entier sup´erieur `a x.
En 1999, Balza-Gomez et al. ont propos´e dans [BGMM99] une m´ethode pour calculer l’enveloppe convexe CHU ou CHL d´ecrite dans la section 2.2. Nous pr´esentons le calcul de CHL. Leur m´ethode atteint une complexit´ en temps de O(log(b′ −b)) et fonctionne en deux ´etapes. Notons AB le segment de droite correspondant `a l’intersection de la droite L avec le domaine vertical D de sorte que A se trouve a` gauche de B. La premi`ere ´etape consiste `a calculer une pr´e-enveloppe associ´ee au segment de droite AB qui comprend les sommets de l’enveloppe convexe finale mais ´egalement des points entiers suppl´ementaires. La seconde ´etape consiste a` parcourir cette pr´e-enveloppe afin d’en supprimer les points suppl´ementaires. Notons que cette m´ethode ne n´ecessite pas que la droite L passe par l’origine du rep`ere.
Nous d´ecrivons tout d’abord le calcul de la pr´e-enveloppe associ´ee au segment de droite AB. Cette pr´e-enveloppe commence au point entier situ´e juste en dessous de A (ou le point A lui-mˆeme) et se termine par le point entier situ´e juste en dessous de B (ou le point B lui-mˆeme). Nous calculons it´erativement cette pr´e-enveloppe. A chaque it´eration, l’algorithme trouve deux points entiers et les concat`ene a` l’enveloppe courante. Ensuite, nous d´eterminons un segment de droite plus petit A′B′ port´e par AB et correspondant au segment de droite consid´er´ `a l’it´eration suivante. L’algorithme se termine lorsque la taille du segment de droite courant est r´eduite `a z´ero. ` ⌊ ⌋ A chaque it´eration, les deux points ajout´es `a la pr´e-enveloppe sont de la forme (xA, yA ) et (xB , ⌊yB ⌋). Ensuite, pour d´eterminer le segment de droite consid´er´ a` l’it´eration sui-vante, nous proc´edons comme suit. Nous consid´erons les deux droites horizontales d’´equa-tion y = ⌈yA⌉ et y = ⌊yB ⌋ ainsi que leurs intersections respectives B′ et A′ avec le segment de droite AB. Nous appliquons alors une rotation d’angle −π/2 radians puis une sym´etrie verticale. Comme la pente de la droite port´ee par A′ et B′ est maintenant strictement sup´erieure `a 1, nous appliquons une transformation unimodulaire U : (x, y) → (x′, y′) de Z2 de fa¸con `a ce que la valeur absolue de la pente de la droite port´ee par les transform´ees de A′ et de B′ soit inf´erieure `a 1 (voir la section 1.1.2). Les ´equations d´efinissant cette x′ = x ⇔ x′ = 10 x y′ = y – ⌊a′⌋x y′ -⌊a′⌋ 1 y o`u a′ repr´esente la pente de la nouvelle droite passant par A′ et B′. Cette transforma-tion correspond `a l’´etape dite de r´eduction car elle diminue la longueur du segment A′B′ a` chaque it´eration.
La figure 2.4 illustre un exemple d’une it´eration de la premi`ere ´etape de l’algorithme. Nous commen¸cons par ajouter `a la pr´e-enveloppe les deux points entiers P et Q et nous d´eterminons le segment de droite A′B′ (figure 2.4.a). Ensuite, nous appliquons une rota-tion d’angle −π/2 radians (figure 2.4.b) et la sym´etrie verticale (figure 2.4.c). Enfin, nous appliquons l’´etape de r´eduction afin de pouvoir r´eit´erer avec le segment de droite A′B′ (figure 2.4.d).
Afin de supprimer les points suppl´ementaires ajout´es `a la pr´e-enveloppe pendant la premi`ere ´etape, nous ex´ecutons la seconde phase de l’algorithme. Nous appliquons la m´e-thode du Graham scan (voir [Gra72] et la section 1.3.2) sur la pr´e-enveloppe afin de construire l’enveloppe convexe enti`ere finale.
Les auteurs ont prouv´e que la premi`ere ´etape effectue O(log(b′ − b)) it´erations, chaque it´eration s’ex´ecutant en temps constant et ajoutant au plus deux points entiers `a la pr´e-enveloppe. De plus, comme les points entiers de la pr´e-enveloppe sont rang´es par abscisses croissantes, la seconde ´etape du Graham scan est suffisante pour calculer l’enveloppe convexe finale en temps lin´eaire suivant le nombre de points de la pr´e-enveloppe. La m´ethode s’ex´ecute donc en O(log(b′ − b)) mais sa complexit´ ne d´epend pas de la taille de la sortie. En effet, le nombre de points suppl´ementaires ajout´es `a la pr´e-enveloppe, et donc le nombre d’it´erations ne peut pas ˆetre exprim´ en fonction du nombre de sommets de l’enveloppe convexe finale. Le nombre d’it´erations de cet algorithme n’est donc pas lin´eaire en le nombre de sommets de l’enveloppe convexe finale.

Notre Nouvelle M´ethode pour le Calcul des En-veloppes Convexes

La m´ethode d´ecrite dans la section 2.4 utilisant la th´eorie des nombres atteint une complexit´ en O(log(b′)) tandis que la m´ethode d´ecrite dans la section 2.5 mettant en oeuvre des techniques de g´eom´etrie algorithmique s’ex´ecute en O(log(b′ − b)), soit la complexit´ optimale. Nous proposons une nouvelle approche pour calculer les enveloppes convexes CHU et CHL qui combine `a la fois la th´eorie des nombres et la g´eom´etrie algorithmique. Notre m´ethode est la premi`ere qui pr´eserve la complexit´ optimale et dont le nombre d’it´erations peut s’exprimer en fonction de la taille de la sortie, notre algorithme est donc adaptatif. En effet, notre algorithme calcule simultan´ement les deux enveloppes convexes en temps lin´eaire suivant le nombre de leurs sommets. En outre, comme l’approche pr´ec´edente, notre m´ethode ne n´ecessite pas que la droite L passe par l’origine du rep`ere, il suffit de connaˆıtre son ´equation et la forme du domaine vertical.

Vue d’Ensemble de Notre Algorithme

L’algorithme que nous proposons calcule simultan´ement les deux enveloppes convexes CHU et CHL par rapport `a la droite L et au domaine born´e D. Chaque enveloppe convexe peut ˆetre d´ecompos´ee en deux parties : une partie gauche et une partie droite. Soit N le vecteur normal de la droite L orient´ vers le haut, c’est-`a-dire dans la direction de CHU . La partie gauche de CHU s’´etend de son sommet le plus `a gauche `a son sommet extr´emal dans la direction −N , de plus petite abscisse. De mani`ere analogue, la partie droite de CHU s’´etend de son sommet le plus `a droite `a son sommet extr´emal dans la direction −N , de plus grande abscisse. Notons que la partie droite et la partie gauche peuvent avoir un sommet en commum. Nous pouvons d´ecrire de fa¸con similaire la partie gauche et la partie droite de CHL. Soient Llef t et Lright les droites verticales respectivement d’´equation x = b et x = b′, bornant le domaine vertical D. La figure 2.5 illustre les diff´erentes parties des enveloppes convexes.
Notre algorithme calcule simultan´ement les sommets des deux enveloppes convexes CHU et CHL et proc`ede en deux phases. La premi`ere phase consiste `a d´eterminer it´erati-vement les sommets des parties gauches de CHU et de CHL depuis Llef t vers la droite. La seconde phase consiste `a calculer les sommets des parties droites de CHU et CHL depuis Lright vers la gauche, en utilisant le mˆeme algorithme. Chaque sommet d´etermin´ durant la premi`ere ou durant la seconde phase est plus proche de la droite de r´ef´erence L que le sommet pr´ec´edent. Par cons´equent, le meilleur point approximant que nous cherchons correspond `a l’un des points extr´emaux des enveloppes convexes.
Notons respectivement CHUL et CHLL les parties gauches des enveloppes CHU et CHL. Nous d´ecrivons la premi`ere ´etape de notre m´ethode a` savoir le calcul de CHUL et CHLL. La seconde ´etape est similaire `a la premi`ere. Notons A1 et B1 les deux premiers sommets de CHUL et de CHLL respectivement. Ces sommets correspondent aux deux points entiers port´es par la droite verticale Llef t situ´es respectivement juste au-dessus et juste en dessous de l’intersection de la droite de r´ef´erence L avec Llef t. Supposons que nous avons trouv´e le i-`eme sommet Ai de CHU et le j-`eme sommet Bj de CHL. Notre m´ethode d´etermine en temps constant le sommet Ai+1 de CHU ou le sommet Bj+1 de CHL. Pour cela, nous cherchons un point entier K appartenant au domaine D tel que la valeur absolue de l’angle entre Ai−1Ai et AiK lorsque K est situ´e au-dessus de L ou entre Bj−1Bj et Bj K lorsque K est situ´e en dessous L est minimal. Dans la section suivante, nous d´etaillons la mani`ere dont nous d´eterminons ce sommet.

Table des matières

Introduction 
1 Pr´eliminaires 
1.1 Espaces Discrets et Transformations Unimodulaires
1.1.1 Introduction aux Espaces Discrets
1.1.2 Transvections
1.2 Outils G´en´eraux de la Th´eorie des Nombres
1.2.1 Identit´e de Bezout
1.2.2 Fractions Continues
1.3 Enveloppes Convexes et Algorithmes
1.3.1 D´efinitions
1.3.2 Panel d’Algorithmes
1.4 D´enombrement
1.4.1 Th´eor`eme de Pick
1.4.2 Le polytope du Probl`eme du Sac `a Dos
2 Approximation d’un Nombre R´eel par un Rationnel `a D´enominateur Born´e 
2.1 Introduction
2.2 Droite Approxim´ee et Enveloppe Convexe Enti`ere
2.3 R´esoudre un Sous-Probl`eme avec les Fractions Continues
2.4 R´esoudre le Probl`eme d’Approximation avec les Fractions Continues
2.4.1 Description de l’Algorithme
2.4.2 Exemple de D´eroulement et Discussion sur l’Algorithme
2.5 Une Seconde Approche Utilisant la G´eom´etrie Algorithmique
2.6 Notre Nouvelle M´ethode pour le Calcul des Enveloppes Convexes
2.6.1 Vue d’Ensemble de Notre Algorithme
2.6.2 D´eroulement de la M´ethode
2.6.3 Analyse de Complexit´e
2.7 Exemples d’Application
2.7.1 Application `a la Compression de Donn´ees
2.7.2 Application `a l’Optimisation Convexe
2.8 Conclusion
3 Introduction `a la Reconnaissance de Plans Discrets 
3.1 Introduction
3.2 Notations et D´efinitions de Base
3.3 Quelques Algorithmes de R´ef´erence
3.3.1 M´ethodes Utilisant la G´eom´etrie Algorithmique
3.3.2 M´ethodes Bas´ees sur la Programmation Lin´eaire
3.3.3 Autres M´ethodes
3.4 Conclusion
4 Nouvelle Approche Efficace pour la Reconnaissance de Plans Discrets 
4.1 Introduction
4.2 La Reconnaissance de Plans Comme un Probl`eme de R´ealisabilit´e
4.3 R´esoudre le Probl`eme de R´ealisabilit´e
4.3.1 Introduction G´en´erale
4.3.2 Calcul du Sous-Gradient
4.4 R´eduction du Domaine de Recherche
4.4.1 Coupes par le Centre de Gravit´e
4.4.2 Am´elioration des Coupes
4.5 Discr´etisation du Domaine de Recherche
4.5.1 ´Etude de l’Espace des Solutions
4.5.2 Am´elioration du Domaine de Recherche Initial
4.5.3 Domaine de Recherche Apr`es Chaque Coupe
4.6 Algorithme R´esum´e et Analyse de Complexit´e
4.6.1 R´esum´e de l’Algorithme
4.6.2 Analyse de Complexit´e
4.7 Algorithme Incr´emental
4.7.1 Motivations et Description de l’Algorithme
4.7.2 Analyse de Complexit´e
4.8 R´esultats Exp´erimentaux et Am´eliorations Pratiques
4.8.1 R´esultats Exp´erimentaux
4.8.2 Am´eliorations Pratiques
4.9 Conclusion
5 Calcul Efficace d’´Epaisseur dans un R´eseau n-dimensionnel 
5.1 Introduction
5.2 D´efinitions
5.3 Le Cas Planaire : Algorithme Existant
5.4 Nouvel Algorithme
5.5 Calcul du Polytope Englobant
5.5.1 Approches Lin´eaires 2D
5.5.2 Une Approche Gloutonne
5.6 Conclusion
Conclusion 

Télécharger le rapport complet