C. R. Acad. Sci. Paris, t. 324, S&k I, p. 1419-1424, 1997

lnformatique thkorique/Computer Science

Analyse locale des droites disc&es. G&&alisation et application h la connexith des plans discrets

Yan Gl?RARD

Lahoratoirr de Logique et d’Informatiqur de Clrrmont-1 (LLAICl),

Dtpartement d”Informatique de l’IUT, Ensemble Univwsitaire drs Cbzeaux, BP nc X6, 63172 AuhiGrr CEDEX.

E-mail : g~rartI@llaic..univ-1,I,rlrrmont.fr

R&urn& L’analyse locale des paliers des droites disc&es de Reveillks conduit naturellement k l’ktude des j7fihre.y d’un plan de Z,‘. Des rkultats locaux concernant l’existence de chemins de connexitt? entre legos voisins permettent la construction du graphe infini de connexitk des [egos. Un algorithme dkterministe pour reconnaitre la connexite d’un graphe infini de p&iode fink permet alors d’en dkterminer la connexitk et d’en dkduire celle du plan.

Local analysis of the digital straight lines.

Generalization and application

to the connectivity of digital planes

Abstract. When studying a ReveiMs digital struight line defined by a double-inequulity (I) : 7 5 ax + by < 2 + I? with (~1, b. r) E N*” and ;i E 22 ~ we are naturally led to study jibers from a digital plane P of Z”. Local results concerning the existence of connectivity paths between neighbowing legos provide a construction of a special injinite graph G bvith jnite period. The deterministic algorithm for recognizing connectivity of infinite graphs we give below also permits us to know the connectivity of P using G.

A bridged English Version

Let D be a digital straight line defined by the double-inequality (I). The level Lj of D (which is denoted Pj as palier in the french part of the Note) is defined as the set of points of D which have j as an ordinate. A level is 4-connected.

Associated to (I), the sequence code(I) : Z - [IO; o,I[ h c aracterizes levels and is defined by

j + (bj - 7) mod a, where mod LC is the remainder of the euclidean division by 0..

Note prksentiie par Maurice NI\!&T.

0764.4442/97/0324 14 I9 0 AcadCmie des Sciences/Elsevier, Paris 1419

Y. Gerard

Other sequences characterizing geometric structures of the levels are defined as follows: (zj) where xj is such that: 7 5 azj + bj < y + a; (length (j)) where length (j) is the cardinality of the level Lj;

(gw(.d) = (Xj-1 - Xj);

and we put I = ak) + (I mod a) and b = aq + (b mod a).

PROPOSITION A. If code(j) < I mod a, then length(j) = & + 1, else length (4) = Q. If code(j) < b mod a, then gap (j) = 4 + 1, else gap(j) = 9. The union Pj U Pj+l is 4-connected if and only if code(j) < I? - b. The union Pj U P,+l is 8-connected if and only if code (j) < l? + a - b. The sequences length, gap, and connectivity, which determine the local geometric structure of

level Lj, are deduced from the arithmetical sequence code. This tool can be used more generally to study digital planes of Z3.

Let P be a digital plane of Z3 and (I) one of its defining double-inequality

(1) : y 5 ax + by + cz < y + r, where (a, b, c: l?) E N*4 and y E Z.

A leaf Fk is defined as the set of points (x, y. Z) E Z3 such that z = k. A fiber Dk of the digital plane P is defined as the intersection between P and leaf Fk. The fiber DI, is a digital straight line of leaf Fk and has a double-inequality (Ik) : y - ck 5 ax + by < y - ck + I?.

The notion of lego of the digital plane P is defined as follows: lego (j, k) is the level of the Jiber DI, with has ordinate j. The lego (;i, k) is of the form [J”(j,k)l ~(j,k.) + Z[j x [lj;j + l[j x [Ik; k + l[\. We denote by length (j, k) the length of lego (j$ k), which is naturally the cardinality of this set.

The function code associated to digital straight lines can be generalized. To the double-inequality (1) we associate the fonction code (1): Z’* + [IO; al[ defined by code (~,(.j~ k) = (bj + ck - y) mod a. It coincides in leaf Fk with the sequence code c,,,(j), associated to fiber Dk, which has (Ik) as Ik a defining double-inequality.

PROPOSITION B . Let r = a& + (I? mod u). y code (j, k) < I mod a, then length (j; k) = Q + 1, else length (j: k) = &. The union lego (j: k) U lego (j + 1) k) is Gconnected if and only if code (j, k) < I’ - b. The union lego (j! k) U lego (j, k t 1) is 6-connected if and only if code (j, k) < r - c. The union lego (j, k) U lego (j + 1, k) is 18-connected if and only if code (j, k) < r + a - b. The union lego (j, k) U lego (j, k t 1) is 18-connected if and only if code (j: k) < r + a - c. The union lego (j, k) U lego (j + 1, k + 1) is 18-connected if and only if code (j, k) < I? - b - c. Zfc > b, the union lego (j, k)Ulego (j - 1, k+ 1) is 18-connected ifand only ifcode (j, k) < l’+b-c. Zf b > c, the union lego (j, k)Ulego (j+l, k-l) is 18-connected ifand only ifcode (j, k) < I’+c-b. The union lego (j, k) U lego (j + 1! k + 1) is 26-connected if and only if code (j, k) < r + a - b - c. Zf a + c 2 b, the union lego (j: k) U lego(j - 1! k + 1) is 26-connected if and only if

code (j! k) < r + a + b - c. rf a + b > c, the union lego (j, k) U lego (j + 1, k - 1) is 26-connected if and only if

code (j, k) < r + a + c - b. The function code (j, k) is a tool for a local analysis of digital planes. A graph of connectivity paths

between legos can be built from the connectivity results obtained in proposition B. Connectivity of this non-finite graph can be studied by using a deterministic algorithm based on double-periodicity of digital planes. Then it is possible to determine whether the digital plane is 6, 18, or 26 connected.

1420

Analyse locale des droites discrhtes...

Partie I : Les droites disc&es (de Reveillb) du plan revisitkes par code

INTRODUCTION ET NOTATIONS. - On s’intkresse dans un premier temps A la structure gComCtrique des droites du plan P2. La dkfinition la plus @n&ale, donnCe par J.-P. Reveiiks, dkrit une droite disc&e D comme l’ensemble de tous les points (z, y) E Z2 solutions d’une double inCgalit6 : (I) : y 5 UT + by < y + r, oti (a> b) E IL*‘, I? E N* et y E 7. Cette double inCgalitC caractkistique (I), que l’on associe B D, n’est pas unique. En changeant le sens des axes, si nkcessaire, on se ramkne au cas d’une droite disc&e descendante, c’est-&dire que l’on peut supposer (a, b) E N*2.

On dkfinit le paliev P, de D comme l’ensemble des points de D d’ordonnke j. Un palier est constitd de points conskutifs et est done 4-connexe. Soit (1) une double-inCgalit6 quelconque caractkristique de D ((1 et b sont seulement supposCs strictement positifs et non nkessairement premiers entre eux) : y < I25 + by < y + r.

A la double inCgalitC (I) on associe la suite code qui type les paliers : codecIJ : 7 -----$ [jO;aj[

j ++ (bj - y) mod a. (Par la notation mod (L, on entend Be reste de la division euclidienne par a.) La suite code a une

@iode a/PGCD(n.b) et elle est construite pour caractkriser la forme locale des paliers. Enfin, on pose r = aQ + (I’ mod u) et b = aq + (b mod u).

PROPOSITION I. - Si code (j) < r mod a, aloes longueur(j) VUL~C Q+l (oLi longueur(j) est le car,dinal du palier I’,) et le palier est dit palier long. Sinon longueur(j) = Q et le palier est dit palier court.

On dkfinit les suites (:Cj), oil zcj est l’unique entier vCrifiant y < azj + bj < y + a, et (dCcalage(j)) = (x-~ - zj).

PROPOSITION 2. - Si code(j) < b mod a, alors dCcalage(j) = Q + 1 et le d&zlage seru dit long. Sinon dtcalage(j) = q et le dkcalage est dit court.

Les suites longueur et dkalage conservent le caractkre pkriodique de la suite code (1) (en rapport avec la pCriodicitC des droites disc&es). Ces deux suites contiennent toute l’information g6omCtrique utile au track d’une droite disc&e D B partir d’un quelconque point de dCpart Mk(5.k;: k).

Exemple. - TracC de la droite D de double-inbgalitk (I) : 2 5 32 + 4y < 13, oti y = 2 et I‘ I= 11. On a alors r mod a = 2, Q = 3, b mod a = 1, q = 1 et code(j) = (4j - 2) mod 3.

PROPOSITIOK 3. - Soit Pj le palier d’ordonntfe j d’une droite discrc?te de double intfgalite’ (I) ; l’union P3 U Pj+l est il-connexe si et seulement si code (l,(j) < r - b ; l’union Pj U aPj+l est 8-connexe si et seulemenr si code cl,(j) < I? + a - b.

nI, code( 3)= 1 longueur( 3)=4 d&alage(3)=1

code(2)=0 longueur(2)=4 dkcalage(2)=2

code( 1)=2 longueur( 1)=3 dkalage( 1 >=l

code(O)=1 longueur(0)=4 dkalage(O)=l

Schema 1. - Construction gComCtrique des paliers PO, PI, P.L et F’J d’aprks les propositions 1 et 2

Scheme 1. - Geometric construction of the levels PO (L is in this part denoted P), PI, Pl, and P3 using proposition A.)

La suite code(j) contient l’information nkcessaire A 1’Ctude de la structure gComCtrique d’une droite disc&e. Ces informations locales sont obtenues par de simples comparaisons (propositions 1,

1421

Y. Gerard

2 et 3). Soit alors (v E N* un entier fix& Notons comparaison,, la suite boolCenne dkfinie par comparaison, (j) = [ code (,j) < ~1’ 1. Les suites palier court-long: dkcalage court-long sont de ce type. II est remarquable de constater que la ditermination de ces suites pkriodiques comparaison,, ne nkcessite pas le calcul de la suite code(j).

PROPOSITION 4. - Soient b’ = b mod n, suppose’ non ~1, et 0 E N” avec IY < a.. Les deux suites comparaison, et comparaisow (associe’es 6 code (,j) = (bj - y) ~rlocl a) se

dkduisent des deux suites comparaison(, ,no,-l fjc) et comparaison(,, I,Iorl ho associkes h code’(j) = (a,j + ((-y) mod 0,)) mod b’.

Les rksultats pour (a> b, 7% (1, b mod a) se dkduisent de ceux pour

(b mod (1. a, -((-y) moda), CL mod 6’. a rrlotl b’),

ce qui provoque une descente de Fermat parallkle au calcul du PGCD de n et b par l’algorithme d’Euclide conduisant B la relation de Bkzout.

Partie II : ConnexitCs des plans discrets

Soit P un plan discret de Z” de double inCgalitC (I) : y 5 nrc+b?j+cz < y+I’, oti (a9 b, c, IY) E N*a .

DEFINITIONS. - On dkfinit la feuille Fk comme l’ensemble des points (:I:: y, 2) E Z” tels que z = k. On appelle fihre DA. du plan discret P l’intersection de P avec la feuille Fk. La fibre DA. est

une droite disc&e de Fk de double idgalitk (Ik) : f̂ - ck 5 n.r: + by < nr - ck + IY. II est possible d’exploiter (Ik). oti n et b ne peuvent pas a priori Ctre supposCs premiers entre eux, car l’&ude des droites disc&es n’a pas Ct6 restreinte aux double-inCgalitCs rkduites.

On definit les legos du plan discret I’ : lego (.j: k) est le palier d’ordonnke j de la fibre L)k.. Les ICgos sont dirigks suivant l’axe des .c :

l%O (3, k:) = [Iqj,k.)qj,k) + l[l x [I.j;j + 1[1 x [pc; k + l[l:

oB 1 est appelke la lonyucz~r du lego (c’est aussi sa longueur en tant que palier de la fibre Ilk). On gkntralise aussi la fonction code. A la double inCgalitC (I), on associe la fonction code (1) :

P -+ [lO:aI[ dkfinie par :

code (r)(.j, k) = (b;j + ck - y) mod a.

Elle co’incide dans la feuille Fk avec la suite code (Ikj(j) associke A la fibre Dk, (de double ikgalid (Jk)).

PROPOSITION 5. - On pose I’ = nQ + (T’ mod a,). Si code (j, A:) < IT mod n, alors lego (j. k) est de longueur Q + 1. Sinon lego (j, k) est de longueur Q.

PROPOSITION 6. L’union lego (j, k) U leg-o (,j + 1, k) est 6-connese si et seulement si code (j, k) < r - b. L’union lego (j, k) U lego (j: k + 1) est 6- connexe si et seulement si cotle (;j. k) < II - c. L’union lego (,j, k:) U lego (.j + 1, k) est l%connexe si et seulement si code (3, k) < r f (I -- b. L’union leg0 (,j, k) U leg0 (j: k + 1) est 18-connexe si et seulement si CO& (j, k:) < r + IL -- c.% L’union Iego (3: k) U lcgo (.j + 1, k + 1) est IX-connexe si et seulement si code (.j, k) < lY -- b - c. L’union lego (j, k) U lego (j + 1, I: + 1) est 26-connexe si et seulement si code (j. k) < I‘ + a - b - c. Sic > b, l’union lego (j% k)Ulego (,j-1, k:+l) est 1%connexe si et seulementsi code (j: k) < r+b-c. Si b 2 c, l’union lego (j, k)lJlego (j+l: k-l) est 18-connexe si et seulementsi code (j: k) < T+c-b.

1422

Analyse locale des droites disct+tes...

Si u + c > b, l’union leg0 (j, k) U leg0 (j - 1. k + 1) est 26connexe si et seulement si code (j, k) < I- + u + b - c.

si n + b > c, l’union leg0 (.j, k:) U leg0 (,j + 1, k - 1) est 26conneXe si et seulement si code (9, k) < I + (1. + c - b.

Les demonstrations sent similaires a celle de la proposition 3. La fonction code (II. k) est un outil pour l’analyse locale des plans discrets.

Le plan discret P de double inegalite (I) : y 5 az + Dy + cz < 7 + I est invariant par les translations T,,, et T, de vecteurs zm,(-b/PGCD((~,, b): a./PGCD(a, b); 0) et ~,(+PGcD(~, c); 0; apGcD(a. +.

On definit alors la partition en pe’riodes du plan discret P ; pour tout couple (71~: n) de Z*, on definit pe’rinde(m. II) = {logo cr)(,j, k)/j E [Ima/PGCD(a, b); (1~1 + l)a/PGCD(cr, b)[l et k E [IM/PGCD(~. c); (n + l)a/PGCD(n, c)[I}. A partir d’une pkriode de P, on peut deduire par T,,, et T,, le reste du plan.

Le probEme de la connexitk d’un plan discret

Pour Ctudier la connexitt d’un plan discret, la premiere idee est de construire, en utilisant la proposition 6, le graphe de connexite des Egos (6. 18 ou 26-connexite au choix). Ce graphe posdde un nombre infini de sommets, ce qui rend non deterministe l’algorithme d’etiquetage pour Ctudier sa connexite. II est en effet impossible de demontrer en un temps fini que deux sommets ne sent pas connexes. Pour avoir un algorithme deterministe, nous utilisons les proprietes du graphe de connlexite des Egos. et en particulier le fait que ce graphe est periodique.

A) PrPsentation d’un algorithme de’terministe pour e’tudier la connesitd d’un graphe periodique de pe’riode jinie (propriete verifiee par le graphe de connexite des Egos).

L’idCe g&&ale de cet algorithme est de rechercher progressivement dans une periode les sommets qui sont connexes.

Partie 1 : Determination des co~leurs initiales. On determine des parties connexes dans la periode, en utilisant un algorithme classique d’ttiquetage,

sans prendre en compte les chemins cxte’rieurs a la ptriode. Chacune de ces parties est appellee couleur. A ce stade, ces couleurs initiales tiennent seulement

compte des chemins inte’rieurs a la periode.

Partie 2 : Fusion apres assemblage de couleurs. On represente une partie connexe s’etendant sur plusieurs periodes par un assemblage de courleurs

sur ces ptriodes. Lorsqu’on decele un chemin de connexite (extkrieur) qui connecte deux couleurs differentes d’une m&me periode, on fusionne les deux couleurs :

,&ape 2.1 : Determination des lois d’assemblage des couleurs. Chaque couleur (notee par exemple couleuri) d’une periode peut &tre connectte a certaines couleurs

dans les periodes voisines. L’ensemble de toutes ces couleurs voisines constitue la loi d’assemblage de la couleur couleur;.

11 est possible qu’une couleur (jaune par exemple) soit connectee a deux couleurs differentes (disons

verte et rouge) d’une meme periode voisine. Ce choix (le vert ou le rouge) traduit l’existence d’un chemin de connexite entre la couleur verte et la couleur rouge (chemin exterieur a la periode et passant par le jaune). On pro&de alors a la fusion des deux couleurs (verte et rouge) et on recommence la partie 2, car les couleurs viennent d’&tre modifiees.

.&tape 2.2 : Assemblage de couleurs suivant les lois determinCes precedemment.

1423

Y. CCrard

Dans cette procedure, on choisit arbitrairement une couleur de depart (par exemple la blew:), et en utilisant les lois d’assemblage, on assemble progressivement sur l’ensemble des periodes unle partie connexe contenant la couleur bleue d’une periode.

L’existence d’un chemin de connexite entre deux couleurs differentes d’une m&me periode apparait comme un choix possible d’assemblage pour cette periode (de la mtme man&e que lorsqu’on determine les lois d’assemblage). On procede alors a la fusion des deux couleurs et on recommence la partie 2 de l’algorithme, l’ensemble des couleurs ayant CtC modifie. A la fin de cette procedure d’assemblage, si l’on n’a pas modifie l’ensemble des couleurs, alors la composante connexe contenant la couleur bleue d’une periode est representee par l’assemblage de couleurs obtenu sur l’ensemble des ptriodes.

B) Terminaison de l’algorithme Expliquons comment on peut effectuer cette procedure d’assemblage en un temps fini. A ce stade, on a simplement ramene l’etude des chemins de connexite (qui peuve:nt &tre

<< infiniment >> longs) a un probleme d’assemblage de couleurs sur l’ensemble des periodes (ensemble de taille infinie et naturellement identifie a ZJ’). Supposons par exemple que l’ensemble des periodes s’identifie a Z2. L’assemblage peut Ctre effect& en un temps fini car il se reduit formellernent au cas suivants :

Cas 1 : La composante connexe contenant la couleur bleue d’une periode est finie. En un temps fini, l’assemblage a partir de la ptriode bleue s’arrete, les lois d’assemblage de

couleurs ne permettant pas d’aller plus loin.

Cas 2 : La composante connexe contenant la couleur bleue d’une periode est infinie. Le nombre de couleurs initiales Ctant fini, on observe au tours de l’assemblage une rCp&t:ition de

couleur en deux periodes differentes 2 E Z2 et en z + T E Z2. On en deduit que deux periodes y E Z* et 7~ + T E .Z2 auront toujours la mCme couleur. L’assemblage de couleurs sur Z2 peut done Ctre restreint a un assemblage sur le cylindre Z*/T.Z.

Cas 2.1 : En un temps fini, l’assemblage de couleurs sur le cylindre s’arrete, les lois d’asse:mblage de couleurs ne permettant pas d’aller plus loin.

Cas 2.2 : Une couleur se repete dans l’assemblage sur le cylindre (suivant le vecteur T'). L’assemblage de couleurs sur Z2/T.Z est alors ramene a un assemblage sur le tore Z2/T.Z $- T'.Z.

Comme le tore est un ensemble fini, l’assemblage des couleurs est optre en un temps fini. Dans tous les cas, l’assemblage des couleurs est (formellement) effectue en un temps fini. 11 aboutit

soit a la diminution du nombre de couleurs (auquel cas on recommence la partie 2), soit a la connaissance de la composante connexe, contenant la couleur bleue d’une periode. Cet algorithme est done deterministe.

Sa complexite est en O((nombre de couleurs initiales)2).

Note remise le 15 janvier 1997, acceptee aprbs revision le 5 fevrier 1997.

Rkfkences bibliographiques

[I] Reveillh J.-P., 1991. G6omCtrie discr&e, calcul en nombres entiers et algorithmique, T&se d’haf.

[2] Gerard Y., 1996. GComCtrie discrkte : Egoland, Preprinf LLAIC 06/96.

1424