Inv. 05963 RR 344

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

Bibliothèque
IRIA

ARCHIVES

UN ALGORITHMÉ ADAPTATIF
DE BALAYAGE DE PEANO

Joel QUINQUETON

Rapport de Recherche N° 344

Février 1979

33p.
UN ALGORITHM ADAPTATIVE OF BALAYAGE DE PÉANO

Joël Quinqueton

IRIA/LABORIA

Résumé :

Ce rapport décrit un algorithme permettant de construire un «balayage de Péano», c'est-à-dire
l'application de [0,1]ⁿ dans [0,1[ réciproque de la célèbre «Courbe de Péano».

Ce balayage de Péano est appliqué à un ensemble de points de [0,1]ⁿ et en donne une image uni-
dimensionnelle. De nombreuses applications de cette technique ont déjà été développées et sont
présentées dans ce rapport.

Abstract :

This paper describes an algorithm which builds a «Peano scanning», i.e. the reciprocal mapping,
from [0,1]ⁿ to [0,1[, of the welknown «Peano curve».

This Peano scanning is applied to a set of points in [0,1]ⁿ and give a 1-dimensional image of it.
Several applications of this technique have already been developed, and are presented in this paper.
# UN ALGORITHME ADAPTATIF DE BALAYAGE DE PEANO

## 1. - INTRODUCTION

En informatique, la réduction du nombre de dimensions est un problème général, qui a des applications dans beaucoup de domaines. Si nous posons le problème comme étant la recherche d'une application de $R^n$ dans $R^q$, avec $q < n$, qui conserve, au moins partiellement, les relations de voisinage, il est naturel d'essayer d'utiliser les courbes emplissant l'espace pour trouver une telle transformation.

Une courbe emplissant l'espace est une application bijective de $[0,1]^n$ dans $[0,1]^n$, qui est continue. On peut montrer qu'elle n'est pas différentiable.

La première fut donnée, sous forme analytique, par PEANO [1] en 1890. Pour cette raison, les courbes emplissant l'espace sont appelées "courbes de Péano". En 1891, HILBERT [2] donna, sous forme géométrique seulement, une autre courbe, basée sur la représentation binaire des nombres (fig. 1).

Les propriétés de ce type de courbe ont été étudiées, d'un point de vue mathématique, par MANDELBROT [3]. Nous retiendrons trois d'entre elles, qui sont intéressantes pour des applications en informatique.

Appelons "courbe de Péano" l'application de $[0,1]$ dans $[0,1]^n$ et "balayage de Péano", de $[0,1]^n$ dans $[0,1]$. La courbe de Péano est continue mais non différentiable. Le balayage de Péano est presque partout continu : l'ensemble de ses discontinuités est un sous ensemble de mesure nulle de $[0,1]^n$. La troisième propriété importante est mise en évidence par la figure 1. C'est le fait que des parties de la courbe sont homothétiques de la courbe complète. Cela permet d'utiliser des procédures récursives pour construire un balayage de Péano.
Ces propriétés ont déjà été utilisées en informatique. Voyons maintenant les différents algorithmes utilisés dans ces applications.

<figure><img src="image_1.png" /><figcaption>Ordre 1</figcaption></figure>

<table><tr><td>1</td><td>2</td><td>3</td></tr><tr><td>-</td><td>+</td><td>+</td><td>-</td></tr><tr><td>6</td><td>5</td><td>4</td></tr><tr><td>-</td><td>+</td><td>+</td><td>-</td></tr><tr><td>7</td><td>8</td><td>9</td></tr></table>

<figure><img src="image_2.png" /><figcaption>Ordre 2</figcaption></figure>

<table><tr><td>1</td><td>2</td><td>3</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td></tr><tr><td>6</td><td>5</td><td>4</td><td>15</td><td>14</td><td>13</td><td>24</td><td>23</td><td>22</td></tr><tr><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>25</td><td>26</td><td>27</td></tr><tr><td>48</td><td>47</td><td>46</td><td>45</td><td>44</td><td>43</td><td>30</td><td>29</td><td>28</td></tr><tr><td>49</td><td>50</td><td>51</td><td>40</td><td>41</td><td>42</td><td>31</td><td>32</td><td>33</td></tr><tr><td>54</td><td>53</td><td>52</td><td>39</td><td>38</td><td>37</td><td>36</td><td>35</td><td>34</td></tr><tr><td>55</td><td>56</td><td>57</td><td>70</td><td>71</td><td>72</td><td>73</td><td>74</td><td>75</td></tr><tr><td>60</td><td>59</td><td>58</td><td>69</td><td>68</td><td>67</td><td>78</td><td>77</td><td>76</td></tr><tr><td>61</td><td>62</td><td>63</td><td>64</td><td>65</td><td>66</td><td>79</td><td>80</td><td>81</td></tr></table>

### 1-A : Courbe de Péano et balayage correspondant

<figure><img src="image_3.png" /><figcaption>Ordre 1</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Ordre 2</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Ordre 3</figcaption></figure>

1 4

2 3

1 2 15 16

4 3 14 13

5 8 9 12

6 7 10 11

1 4 5 6 59 60 61 64

2 3 8 7 58 57 62 63

15 14 9 10 55 56 51 50

16 13 12 11 54 53 52 49

17 18 31 32 33 34 47 48

20 19 30 29 36 35 46 45

21 24 25 28 37 40 41 44

22 23 26 27 38 39 42 43

### 1-B : Courbe de Hilbert et balayage correspondant

FIGURE 1 : EXEMPLES DE COURBES ET BALAYAGES DE PEANO
## 2. - HISTORIQUE

Il y a 2 sortes d'applications des courbes emplissant l'espace en Informatique, liées aux deux propriétés de ces courbes précédemment soulignées : d'une part la continuité de la courbe de Péano, d'autre part la continuité presque partout du balayage de Péano.

Le fait qu'une courbe de Péano soit une application continue de $[0,1]$ dans $[0,1]^n$ a été utilisé dans 2 domaines : la transmission de données et l'analyse numérique.

En transmission de données, le problème est de transmettre un seul nombre au lieu de n, de façon à réduire la bande passante de la porteuse. BIALLY [4] a proposé d'utiliser la courbe de Péano pour transformer les n nombres en un seul, et de restaurer les n nombres après transmission : grâce à la continuité de la courbe, les n nombres restaurés seront toujours dans le voisinage des données de départ.

Le programme construit des diagrammes, de taille finie, chacun d'eux correspondant à un algorithme permettant de convertir n valeurs en une seule, ou vice versa.

Ces diagrammes, appelés "diagrammes d'état", sont construits à partir du dessin de base de la courbe.

Divisons l'hypercube $[0,1]^n$ en $m^n$ parties égales. Toute courbe joignant les centres de ces $m^n$ hypercubes de façon que chacun soit relié à 2 autres qui lui sont adjacents peut être le dessin de base d'une courbe de Péano. La seule contrainte est que les deux extrémités de la courbe soient les centres d'hypercubes situés sur les côtés de $[0,1]^n$.

Les états des "diagrammes d'état" sont les matrices nxn représentant les transformations (symétries, rotations) que peut subir ce destin de base en passant de l'ordre k à k+1.

Les états sont reliés entre eux par des flèches, où sont indiqués, écrits en base de numération n :

- le n-uplet des $k^{\text{ième}}$ digits de chaque coordonnée

- le $k^{\text{ième}}$ groupe de n digits de l'image dans $\mathbb{R}$ (entre parenthèses)
La figure 2 montre le diagramme d'état de la courbe de Hilbert (n=2, m=2).

<figure><img src="image_6.png" /><figcaption>FIGURE 2 : DIAGRAMME D'ETAT DE BIALLY POUR LA COURBE DE HILBERT (n=2, m=2)</figcaption></figure>

Le problème traité par Bially est assez voisin du problème des codes GRAY [5].

Le deuxième domaine d'application de la courbe de Péano est l'analyse numérique. BUTZ [6,7,8] a proposé une méthode itérative pour résoudre ces problèmes multidimensionnels pour lesquels les méthodes classiques échouaient. Le domaine fonctionnel multidimensionnel est ramené à une dimension par une courbe de Péano. L'application qui permet de passer de la valeur unidimensionnelle de la variable à la valeur de la fonction de n variables est la composée de cette fonction et d'une fonction continue (la courbe de Péano), ce qui autorise à appliquer des méthodes itératives unidimensionnelles.

Son algorithme calcule m digits de chaque coordonnée du point dans [0,1]^n à partir de m groupes de n digits de la valeur dans [0,1]. L'algorithme utilise seulement les opérateurs "ou exclusif", "complément" et "décalage" et peut être facilement inversé pour calculer un nombre à partir de n nombres. Deux courbes sont proposées : la courbe de Péano [6], utilisant des digits ternaires, et la courbe de Hilbert [7,8] utilisant des digits binaires.
La continuité presque partout du balayage de Péano a été utilisée pour quatre applications principales : reconnaissance des formes statistique, visualisation de sorties de programmes, classification et traitement d'images.

En reconnaissance des formes statistique, KANAL et al [9], suivis par G.T. TOUSSAINT [10] proposèrent de modéliser une forme binaire multidimensionnelle par une chaîne de Markov le long d'une courbe de Péano. Cela n'est pas équivalent à un modèle probabiliste multidimensionnel, mais c'est une bonne approximation, grâce à la quasi-continuité du balayage de Péano. Les auteurs ne donnent aucune précision sur l'algorithme.

En visualisation de sortie de programmes, le problème de la représentation d'une fonction de n variables réelles sur un écran bidimensionnel n'est pas simple. PATRICK et al [11] ont proposé de transformer le domaine fonctionnel à n dimensions en un intervalle de R, au moyen d'un balayage de Péano.

L'algorithme est basé sur la construction de Péano [1], avec une généralisation à toute base de numération impaire m :

soient $(e_j), j=1 \text{ à } n$, les n coordonnées du point

$$e_j = \sum_{\ell=1}^{k} \alpha_{j\ell} m^{\ell-1} \quad (\text{décomposition en base m})$$

L'image du point par le balayage sera :

$$e = \sum_{j=1}^{j=n} \sum_{\ell=1}^{\ell=k} \beta_{j\ell} m^{kn-j\ell}$$

où $\beta_{j\ell} = \alpha_{j\ell}$ si $A_{j\ell}$ pair, et $m-1-\alpha_{j\ell}$ si $A_{j\ell}$ impair

$$A_{j\ell} = \sum_{r=0}^{\ell-1} \sum_{s=1}^{n} \alpha_{sr} - \sum_{r=0}^{\ell-1} \alpha_{jr} + \sum_{s=0}^{j-1} \alpha_{sl}$$

En classification, le problème est de trouver la structure d'un ensemble de données. ALEXANDROV [12] propose de représenter les données dans $R^+$, au moyen d'un histogramme le long d'un balayage de Péano. Les pics de cet histogramme seront les noyaux des classes de la partition. Le balayage de Péano est construit à l'aide d'un algorithme récursif à deux niveaux : construction récursive du balayage élémentaire à n dimensions à partir de celui à 2 dimensions, et construction récursive du balayage complet à partir du balayage élémentaire.
La finesse du balayage est uniforme et déterminée heuristiquement.

Une autre méthode de classification a été proposée par J.C. SIMON et J. QUINQUETON [13], qui consiste à combiner deux balayages, se déduisant l'un de l'autre par une translation telle que les discontinuités ne se recouvrent pas. L'algorithme utilisé est celui qui est décrit plus loin dans ce rapport.

En traitement d'images, STEVENS et LEHAR [14] ont proposé d'explorer une image de taches suivant un balayage de Péano. Un filtrage approprié permet de compter les taches et de calculer leur taille moyenne. Dans ce cas, le balayage de Péano est généré par hardware (taille et finesse fixée).

Ce tour d'horizon des divers algorithmes utilisés pour construire une courbe ou un balayage de Péano met en évidence deux types de méthodes : les méthodes analytiques (Bially, Butz, Patrick et al) et les méthodes récursives (Alexandrov, Simon et Quinqueton). Nous allons maintenant voir pourquoi, en dépit de leur complexité élevée, les méthodes récursives sont intéressantes en classification.
### 3. - UN ALGORITHM RECURSIF ADAPTATIF

En classification, et plus généralement en analyse de données on a à considérer un grand ensemble de données. Si nous voulons transformer le problème, comme dans notre cas, nous devons calculer l'image de chaque point par la transformation. Comme cette transformation doit préserver le voisinage de points, nous pouvons les grouper, hiérarchiquement, afin d'éviter de faire plusieurs fois les mêmes opérations. C'est possible en utilisant un algorithme récursif pour construire un balayage de Péano.

Nous verrons aussi que, du point de vue de la complexité, les algorithmes récursifs sont intéressants car ils sont moins dépendants que les algorithmes analytiques du nombre de points, bien qu'ils soient plus dépendants du nombre de dimensions de l'espace.

Donc, l'algorithme que nous allons maintenant décrire en détails est basé sur la récursivité d'un balayage de Péano. Nous utilisons cette propriété locale-ment : la finesse du balayage dépend de la densité locale des données.

L'idée d'un tel algorithme "adaptatif" fut déjà utilisée dans une autre application : la visualisation de sorties de programmes [10]. Mais, dans ce cas, la finesse était la même pour tout le balayage, et non pas définie localement.

Passons maintenant à la description de l'algorithme.

### 4. - DESCRIPTION DE L'ALGORITHM

L'algorithme récursif peut être divisé en plusieurs parties :

Les variables du programme sont :

$n$ = dimension de l'espace

$k$ = finesse du balayage ($k < k_{\text{max}}$)

$s$ = n° de la "face de sortie" ($1 \le s \le n$)

$e$ = n° de la "face d'entrée" ($1 \le e \le n$)

$k_e$ = valeur minimale de k pour laquelle le balayage est entré par la face e.

$k_s$ = valeur minimale de k pour laquelle le balayage est sorti par la face s.
$x_{ij} = j^{\text{ème}}$ bit de la $i^{\text{ème}}$ coordonnée (du centre de l'hypercube courant)

LI = liste des points de l'hypercube courant.

N = nombre de points dans l'ensemble de données

Z = numéro sur le balayage de l'hypercube courant

Décrivons maintenant les différentes parties de l'algorithme.

"FOCUS" :

Teste la liste LI pour savoir s'il est ou non nécessaire de "zoomer",
i.e. d'augmenter localement la finesse de balayage.

Si oui, il appelle "SCAN", après avoir calculé les arguments de façon que
le balayage obtenu soit bien continu.

Si non, il met en mémoire le numéro, sur le balayage, de l'hypercube courant,
à l'adresse des points situés dans cet hypercube, c'est-à-dire ceux de la liste LI.

PROCEDURE "FOCUS" (s, k<sub>s</sub>, LI)

BEGIN ;

IF ('TEST'=TRUE) THEN ;

k := k+1

$x_{ek} := 1-x_e k_e$

IF ($x_{sk} = x_{s,1}^k$) THEN ;

'SCAN' (n,s)

ELSE ;

'SCAN' (n,e)

END ;

(FOCUS' (s,k<sub>s</sub>, 'EXTR'))

k := k-1

ELSE ;
    n(k<sub>max</sub> -k+1)

Z := Z+2

'OUTPUT'

Mémorisation. Si $LI \neq \emptyset$

END ;

END ;
"SCAN" - "TREE"

Un balayage élémentaire de dimension n peut être considéré comme composé
de deux balayages de dimension n-1 symétriques par rapport à une des coordonnées.
Cette coordonnée est entrée comme argument (ℓ). Chaque balayage élémentaire de
dimension n-1 est engendré par "TREE", de façon récursive. L'élément du balayage
de dimension n correspondant à la traversée du plan de symétrie est engendré par
"SCAN".

Chaque élément de balayage engendré donne lieu à un appel de "FOCUS", pour
augmenter, si nécessaire, la finesse du balayage.

```pascal
PROCEDURE 'SCAN' (P,ℓ)
BEGIN ;
  'TREE' (P)
  'FOCUS' (ℓ,k,'EXTR')
    x_{ℓk} := 1-x_{ℓk}
  e := ℓ
  k_e := k
  'TREE' (P)
END ;
```
```pascal
PROCEDURE 'TREE' (m)
BEGIN ;
  IF (m≠0) THEN ;
    'TREE' (m-1)
    IF (m≠ℓ) THEN
      'FOCUS' (m,k, 'EXTR')
        x_{mk} := 1-x_{mk}
      e := m
      k_e := k
      'TREE' (m-1)
    END ;
  END ;
END ;
```
"EXTR"

Cette procédure est une fonction. Elle extrait de la liste LI la sous liste appartenant à l'hypercube courant, prend pour valeur cette sous liste et donne à LI la valeur de la sous liste restante.

La première version, programmée en LISP, consistait à diviser LI en deux sous listes, LS (points se trouvant dans l'hypercube) et LC (autres points). La valeur de EXTR est LS. La valeur de LI à la fin est LC.

La version programmée en FORTRAN consiste à réordonner la liste LI, en plaçant en tête les points appartenant à l'hypercube. La valeur de EXTR est la liste de tête, et celle de LI à la fin est la liste de queue. L'avantage de cette procédure est de réduire les permutation aux minimum, et d'être plus économique en place mémoire, puisque seuls les pointeurs de début et de fin de liste sont empilés.

Nous donnons en annexe les listings LISP et FORTRAN de la fonction EXTR.
"TEST"

Cette fonction à valeur booléenne décide, en fonction de la liste LI,
s'il faut on non augmenter la finesse. Si le nombre d'éléments de la liste LI
est inférieur à un seuil donné au départ, TEST prend la valeur FALSE. Sinon,
TEST=TRUE.

INITIALISATION

Après la lecture des données, et la constitution de la liste LI, le pro-
gramme initialise les variables

BEGIN ;
FOR i=1 to n AND j=1 Kmax D Ø
  x: j = 0
END ;

x = 1
Z=0

k=1 ; e=1 ; k =1
'FOCUS' (2, 1, LI).

END ;
Tout se passe donc comme si tous les points étaient dans un élément du premier balayage engendré, défini par $e = 1$ et $s = 2$.

L'hypercube contenant tous les points correspondra donc à la valeur $k = 2$. Cet artifice permet d'éviter d'utiliser la valeur $k=0$ qui est incommode pour les adresses de tableaux.

## 5. - FONCTIONNEMENT DE L'ALGORITHM

Nous allons suivre pas à pas le fonctionnement de l'algorithme sur des données simples, bidimensionnelles, permettant une visualisation facile. La figure 3 représente ces données.

Pour la procédure TEST, nous supposerons que celle-ci vaut .TRUE. s'il y a plus d'un élément dans la liste LI. S'il y a 0 ou 1 élément, TEST = FALSE.

<figure><img src="image_7.png" /><figcaption>FIGURE 3 : LES DONNES TEST</figcaption></figure>

Le programme commence par initialiser les variables (INIT). Au premier appel de la procédure FOCUS, la liste LI est l'ensemble de tous les points, c'est-à-dire que le programme voit l'ensemble des données. (voir tableau 1).

<table><caption>Tableau 1</caption><thead><tr><th>appels de procédures</th><th>k</th><th>z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>INIT</td><td>1</td><td>0</td><td>1000</td><td>0000</td><td>1</td><td>1</td></tr><tr><td>FOCUS (2,1,{1,2,3,4,5,6,7})</td><td>2</td><td></td><td>0</td><td></td><td></td><td></td></tr><tr><td>SCAN (2,2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,2,Ø)</td><td></td><td>16</td><td>1</td><td></td><td>1</td><td>2</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
Le programme a augmenté de 1 la finesse du balayage. Ayant trouvé un carré vide, il ne l'augmentera pas davantage dans cette zone ; z est donc incrémenté de $2^4 = 16$. La procédure TREE (2) est terminée. Il va maintenant y avoir appel de FOCUS dans le carré suivant. (voir tableau 2).

<table><thead><tr><th></th><th>k</th><th>z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(INIT)</td><td>2</td><td>16</td><td>1100</td><td>0000</td><td>1</td><td>2</td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)...</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,2,{3,4,5,6,7})</td><td>3</td><td></td><td>0</td><td></td><td></td><td></td></tr><tr><td>SCAN (2,2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3,Ø)</td><td></td><td>20</td><td>1</td><td></td><td>1</td><td>3</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

## Tableau 2

Nous constatons que le programme a reproduit la procédure dont nous avons parlé plus haut ; z a cette fois été incrémenté de $2^2 = 4$. Il va donc maintenant y avoir appel de Focus dans le carré suivant. (voir tableau 3).

<table><thead><tr><th></th><th>k</th><th>z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(INIT)</td><td>3</td><td>20</td><td>1110</td><td>0000</td><td>1</td><td>3</td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)...</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,3,{5,7})</td><td>4</td><td></td><td>0</td><td></td><td></td><td></td></tr><tr><td>SCAN (2,2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,4,Ø)</td><td></td><td>21</td><td>1</td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,4,{7})</td><td></td><td>22</td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,4,Ø)</td><td></td><td>23</td><td>0</td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

## Tableau 3
La procédure SCAN (2,2) est maintenant terminée. Nous retournons donc dans FOCUS (2,3,{5,7}). Mais il reste le dernier carré à traiter. C'est le but de l'instruction suivante, qui est un appel à FOCUS, après lequel la finesse a diminuer de 1 et nous allons passer au carré suivant. (voir tableau 4)

<table><caption>Tableau 4</caption><thead><tr><th></th><th>k</th><th>z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(INIT)<br>(FOCUS)<br>(SCAN)<br>(FOCUS)<br>(SCAN)<br>(FOCUS)<br>FOCUS (2,3,{5})</td><td>4<br>3</td><td>24</td><td>1110</td><td>0001<br>1</td><td>1<br>2</td><td>4<br>3</td></tr><tr><td>TREE (2)<br>TREE (1)<br>TREE (0)<br>FOCUS (1,3,{4,6})</td><td>4</td><td></td><td></td><td>0</td><td></td><td></td></tr></tbody></table>

Nous voyons ici le rôle de l'instruction $x_{ek} = 1 - x_{ek_e}$ : elle initialise les coordonnées du premier carré du balayage local, après avoir augmenté la finesse de 1. C'est donc cette instruction qui garantit la continuité du balayage engendré.

Le programme va maintenant appeler SCAN ; après avoir calculé les arguments (tableau 5) :

$$k=4, s=1, k_s = 3 : x_{14} = 0 \neq x_{13} = 1$$
C'est donc SCAN (n,e) qui va être appelée, soit SCAN (2,2).

<table><caption>Tableau 5</caption><thead><tr><th></th><th>k</th><th>z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>e<sub>ke</sub></th></tr></thead><tbody><tr><td>(INIT)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(TREE)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(TREE)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(FOCUS)</td><td>4</td><td>24</td><td>1110</td><td>0010</td><td>2</td><td>3</td></tr><tr><td>SCAN (2,2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,4,{4})</td><td></td><td>25</td><td>1</td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,4,{6})</td><td></td><td>26</td><td></td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,4,Ø)</td><td></td><td>27</td><td>0</td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3,Ø)</td><td></td><td>28</td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,2,{3})</td><td></td><td>32</td><td></td><td></td><td>1</td><td>2</td></tr><tr><td></td><td></td><td>2</td><td></td><td></td><td></td><td>2</td></tr></tbody></table>
Le programme vient de terminer la procédure FOCUS (2,2,{3,4,5,6,7}). Il retourne donc dans SCAN (2,2). Après avoir fait progresser la valeur de $x_{22}$ afin de se placer dans le carré suivant, il va appeler TREE (2) comme cela apparaît sur le tableau 6.

<table><thead><tr><th></th><th>k</th><th>Z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(INIT)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(FOCUS)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>(SCAN)</td><td>2</td><td>32</td><td>1110</td><td>0110</td><td>2</td><td>2</td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,2,Ø)</td><td></td><td>48</td><td>0</td><td></td><td>1</td><td>2</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,1,{1,2})</td><td>3</td><td></td><td>1</td><td></td><td></td><td></td></tr><tr><td>SCAN (2,1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,3,Ø)</td><td></td><td>52</td><td></td><td>0</td><td>2</td><td>3</td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3,Ø)</td><td></td><td>56</td><td>0</td><td></td><td>1</td><td>3</td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,3,Ø)</td><td></td><td>60</td><td></td><td>1</td><td>2</td><td>3</td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,1,{1,2})</td><td>4</td><td></td><td></td><td>0</td><td></td><td></td></tr></tbody></table>

Tableau 6

Le programme en est au dernier carré de finesse k=3. Ce carré a été trouvé contenant 2 points. Le programme passe donc à la finesse k=4 et initialise correctement les coordonnées $x_{14}$ et $x_{24}$ (tableau 7).
<table><caption>Tableau 7</caption><thead><tr><th></th><th>k</th><th>Z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(INIT)</td><td rowspan="10">4</td><td rowspan="10">60</td><td rowspan="10">1000</td><td rowspan="10">0110</td><td rowspan="10">2</td><td rowspan="10">3</td></tr><tr><td>(FOCUS)</td></tr><tr><td>(FOCUS)</td></tr><tr><td>(FOCUS)</td></tr><tr><td>(FOCUS)</td></tr><tr><td>SCAN (2,2)</td></tr><tr><td>TREE (2)</td></tr><tr><td>TREE (1)</td></tr><tr><td>TREE (0)</td></tr><tr><td>FOCUS (1,4,Ø)</td></tr><tr><td>TREE (0)</td></tr><tr><td>FOCUS (2,4,{2})</td></tr><tr><td>TREE (2)</td><td rowspan="4">62</td></tr><tr><td>TREE (1)</td></tr><tr><td>TREE (0)</td></tr><tr><td>FOCUS (1,4,Ø)</td></tr><tr><td>TREE (0)</td></tr><tr><td>FOCUS (2,1,{1})</td></tr><tr><td>END</td><td>3</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>2</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

A l'issue de l'algorithme, nous obtenons donc les coordonnées unidimensionnelles des 7 points de l'ensemble (fig. 4).

<figure><img src="image_8.png" /><figcaption>Figure 4</figcaption></figure>

Cette description du fonctionnement de l'algorithme a mis en évidence le caractère recursif de celui-ci.

Nous voudrions compléter cette description en étudiant localement le cas multidimensionnel (n>2).
Soit donc un hypercube n-dimensionnel, contenant une certaine liste de points LI, telle que le programme va augmenter la finesse k d'une unité. Afin de ne pas alourdir la description, nous supposerons que les sous listes extraites à chaque appel de "EXTR" sont telles que "TEST" prend la valeur "FALSE", c'est-à-dire que le programme n'augmente plus la finesse du balayage.

Nous allons suivre, pour n=4, le fonctionnement des procédures "SCAN", et "TREE", étape par étape, pour des conditions initiales données (voir tableau 8).

<table><caption>Tableau 8</caption><thead><tr><th>PROCEDURES</th><th>k</th><th>Z</th><th>x<sub>1j</sub></th><th>x<sub>2j</sub></th><th>x<sub>3j</sub></th><th>x<sub>4j</sub></th><th>e</th><th>k<sub>e</sub></th></tr></thead><tbody><tr><td>(FOCUS)</td><td>3</td><td></td><td>100</td><td>010</td><td>001</td><td>000</td><td>3</td><td>2</td></tr><tr><td>SCAN (4,3)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (4)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (3)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td>1</td><td>3</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td>1</td><td>3</td></tr><tr><td></td><td></td><td></td><td>0</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (4,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td><td>4</td></tr><tr><td>TREE (3)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td>1</td><td>3</td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (2,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td>2</td><td>3</td></tr><tr><td></td><td></td><td></td><td></td><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (1,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td>1</td><td>3</td></tr><tr><td></td><td></td><td></td><td>0</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (3,3, 'EXTR')</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td>3</td><td>3</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (4)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (3)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (2)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (1)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>TREE (0)</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>FOCUS (...)</td><td>+1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody><tfoot><tr><td colspan="9">(identique au premier appel de TREE (4))</td></tr></tfoot></table>
Le programme, après avoir terminé TREE (4), retourne dans SCAN, qui fait progresser la 3e coordonnée, qui n'avait pas été modifiée jusqu'alors. Puis il va de nouveau appeler TREE (4) pour la seconde partie du balayage. Nous voyons ici apparaitre la structure symétrique de ce balayage. L'hyperplan de symétrie est d'équation $x_3 = C^{te}$.

Cette description du fonctionnement du programme a mis en évidence le rôle de certaines instructions de la procédure FOCUS pour assurer la continuité du balayage obtenu. Nous allons maintenant revenir sur ces instructions, afin de démontrer que l'on obtient effectivement un balayage de Péano, au sens ou il a été défini au début de cet article.

## 6. - JUSTIFICATION DE L'ALGORITHME

Nous devons formaliser la définition d'un balayage de Péano que nous avons donnée dans le premier paragraphe. Reprenant la terminologie de HAWKES [18], nous utiliserons le concept de "cylindre b-adique".

Soit b et p deux entiers. Un cylindre b-adique de rang p, dans $R^n$, est un hypercube semi-ouvert de côté $b^{-p}$ dont tous les sommets sont de la forme $(k_1 b^{-p}, k_2 b^{-p}, \dots, k_n b^{-p})$ pour des valeurs entières de $(k_1, \dots, k_n)$.

Comme l'hypercube est semi-ouvert, il contient un seul de ses sommets, la borne inférieure dans chaque direction.

Nous appelerons *coordonnées* du cylindre b-adique le n-uplet correspondant à ce sommet.

Dans la suite, nous prenons les cylindres seulement dans $[0,1]^{\mathbb{N}}$. Soit $\mathcal{U}(b,n,p)$ l'ensemble de tous les cylindres b-adiques de rang p dans $[0,1]^{\mathbb{N}}$. Si nous écrivons en base b les coordonnées d'un u à $\mathcal{U}(b,n,p)$ nous obtenons une suite $\{(x_{ij}, j=1,p) \ i=1,n) \text{ où } x_i = \sum_{j=1}^{p} x_{ij} b^{-j} \text{ est la i^{ème} coordonnée de u, et } x_{ij} \text{ est un nombre entier inférieur à b.}$

Donc, nous désignerons un cylindre, soit par une lettre, u, soit par la séquence $((x_{ij}, j=1,p) \ i=1,n)$.
## DEFINITION 1

Un balayage de Péano d'ordre p est une application $\varphi(b,n,p;.)$ de $U(b,n,p)$ dans $U(b,1, np)$ qui a les propriétés suivantes :

a) $\varphi$ est bijective (1)

b) l'application reciproque $\varphi^{-1}$ est continue (2) :

$$ \forall \varepsilon > b^{-np} \quad \exists \eta \text{ tel que } d(\varphi(u), \varphi(v)) < \eta \Rightarrow d(u,v) < \varepsilon $$

où la distance d est la distance entre les vecteurs de coordonnées de deux cylindres.

c) soit $u_p \in U(b,n,p)$ et $u_r \in U(b,n,r)$ :

$$ \forall r \le p : \quad \bigcup_{u_p \subset u_r} \varphi(b,n,p; u_p) = \varphi(b,n,r; u_r) \in U(b,1,nr) \quad (3) $$

où $\varphi$ est un balayage de Péano d'ordre r.

La condition (3) est une formalisation de la récursivité du balayage.

Si nous l'exprimons en termes de coordonnées binaires, nous obtenons :

si $(Z_j, j=1, np)$ est l'image de $((x_{ij}, j=1, p), i=1, n)$ par $\varphi$

alors $(Z_j, j=1, nr)$ doit être celle de $((x_{ij}, j=1, r), i=1, n)$ par $\varphi$.

Nous devons maintenant montrer que l'ensemble $\Phi(b,n,p)$ des balayages de Péano d'ordre p n'est pas vide. La démonstration générale sortirait du cadre de cet article. Nous considérons seulement le cas $b=2$, en relation avec notre algorithme.

La démonstration sera faite en 2 étapes :

a) $\forall n, \Phi(2,n,1) \neq \emptyset$

b) si $\Phi(2,n,p) \neq \emptyset$, alors $\Phi(2,n,p+1) \neq \emptyset$

## ETAPE 1 : le cas $p=1$

Nous allons ici montrer plus que la simple existence d'un balayage de Péano d'ordre 1, en le soumettant à plusieurs contraintes.

Soit $\varphi(2,n,1;.)$ un balayage de Péano d'ordre 1 : c'est une application de $U(2,n,1)$ dans $U(2,1,n)$.

Nous appellerons **case d'entrée** l'élément $u \in U(2,n,1)$ tel que
$$ \varphi(2,n,1;u) = (0) \quad \forall u \in U(2,1,n). $$
La case de sortie sera $v \in U(2,n,1)$ tel que
$$ \varphi(2,n,1;v) = (1-2^{-n}) \in U(2,1,n). $$
Les contraintes sont, exprimées en terme de coordonnées binaires :

u = (α₁, ..., αₙ), les αᵢ étant donnés dans {0,1}

v = (β₁, ..., βₙ) où s ∈ {1, ..., n} est donné et βₙ est donné dans {0,1}

Le sous ensemble $O(s) = \{(x₁, ..., xₙ) ∈ U(2,n,1) ; x_s = β_s\}$ est appelé
<u>face de sortie du balayage.</u>

Nous voulons montrer ici que l'ensemble des balayages de Péano de case d'entrée et de face de sortie donnée n'est pas vide.

Pour n=1, la fonction identité est un tel balayage, sauf si $α_s = β_s$.

Nous examinerons donc le cas n=2 : il y a en tout 16 cas possibles (4 cases d'entrée et 4 faces de sortie), parmi lesquels nous distinguerons deux éventualités : $α_s = β_s$ et $α_s ≠ β_s$. Le tableau 9 donne toutes les possibilités.

<table><caption><u>Tableau 9</u> : le cas bidimensionnel</caption><thead><tr><th>Objet (xᵢ, i=1,2) ∈ U(2,2,1)</th><th>Image (Z, j=1,2) ∈ U(2,1,2)</th><th colspan="2">Relations entre les éléments de U(2,2,1) cas α<sub>s</sub> = β<sub>s</sub> cas α<sub>s</sub> ≠ β<sub>s</sub></th></tr></thead><tbody><tr><td>(α₁, α₂)</td><td>(00)</td><td>donné</td><td>donné</td></tr><tr><td>(α₁, α₂)</td><td>(01)</td><td>α<sub>s</sub> = 1 - α<sub>s</sub><br>a<sub>j</sub> = α<sub>j</sub>, si j≠S</td><td>a<sub>j</sub> = 1 - α<sub>j</sub>, si j≠S<br>a<sub>s</sub> = α<sub>s</sub></td></tr><tr><td>(β₁, β₂)</td><td>(10)</td><td>b<sub>j</sub> = 1 - a<sub>j</sub>, si j≠S<br>b<sub>s</sub> = a<sub>s</sub></td><td>b<sub>s</sub> = 1 - a<sub>s</sub>,<br>b<sub>j</sub> = a<sub>j</sub>, si j≠S</td></tr><tr><td>(β₁, β₂)</td><td>(11)</td><td>β<sub>s</sub> = 1 - b<sub>s</sub><br>β<sub>j</sub> = b<sub>j</sub>, si j≠S</td><td>β<sub>j</sub> = 1 - b<sub>j</sub>, si j≠S<br>β<sub>s</sub> = b<sub>s</sub></td></tr></tbody></table>

Nous voulons maintenant montrer que, si un balayage de dimension n-1 existe, sous les contraintes précédentes, alors il en existe un de dimension n.
Comme dans le cas bidimensionnel, nous distinguerons deux cas : $\alpha_s = \beta_s$ et $\alpha_s \neq \beta_s$.

Dans le premier cas ($\alpha_s = \beta_s$), soit $m \neq s$ : m sera l'axe du balayage. D'après notre hypothèse, il existe un balayage de dimension $n-1$, $\psi_1$, dont la case d'entrée est $(\alpha_1, \dots, \alpha_{m-1}, \alpha_{m+1}, \dots, \alpha_n)$ et dont la case de sortie $(a_1, \dots, a_{m-1}, a_{m+1}, \dots, a_n)$ est telle que $a_s = \beta_s$.

Le balayage de dimension $n$, $\varphi$, sera alors défini par :

a) $\varphi(2,n,1; (x_1, \dots, x_{m-1}, \alpha_m, x_{m+1}, \dots, x_n)) = (z_j, j=1,n) \in \mathcal{U}(2,1,n)$ où $Z_1 = 0$ et $(Z_2, \dots, Z_n)$ est l'image par $\psi_1$ de $(x_1, \dots, x_{m-1}, x_{m+1}, \dots, x_n)$

b) $\varphi(2,n,1; (x_1, \dots, x_{m-1}, 1-\alpha_m, x_{m+1}, \dots, x_n)) = (t_j, j=1,n) \in \mathcal{U}(2,1,n)$ où $t_1 = 1$ et $(t_2, \dots, t_n)$ est l'image de $(x_1, \dots, x_{m-1}, x_{m+1}, \dots, x_n)$ par le balayage de dimension $n-1$, $\psi_2$, dont la case d'entrée est $(a_1, \dots, a_{m-1}, a_{m+1}, \dots, a_n)$ et dont la face de sortie est telle que $x_s = \beta_s$.

$\psi_2$ est déduit de $\psi_1$ en prenant l'ordre inverse des cylindres.

Nous avons maintenant défini un balayage de dimension $n$. On vérifie aisément que les conditions (1) et (2) de la définition 1 sont vérifiées. (3) est également évidente, car $p=1$.

Dans le cas $\alpha_s \neq \beta_s$, nous pouvons construire $\varphi$ de la même manière, en choisissant $S$ comme axe du balayage.

La démonstration est ainsi terminée.

## ETAPE 2 : de $p$ à $p+1$

Nous partons ici de l'hypothèse qu'il existe un balayage d'ordre $p$, soit $\varphi(2,n,p;\cdot)$.

Soit $u \in \mathcal{U}(2,n,p+1)$. Il lui correspond $v \in \mathcal{U}(2,n,p)$ tel que $u \le v$.

Soit $(\ell 2^{-np}) \in \mathcal{U}(2,1,\ell p)$ l'image de $v$ par $\varphi$. Nous définissons $v^+$ et $v^-$ comme les éléments de $\mathcal{U}(2,n,p)$ vérifiant les conditions :

$$ \varphi(2,n,p;v^+) = ((\ell+1) 2^{-np}) $$

$$ \varphi(2, \ell, n, p; v^-) = ((\ell-1) 2^{-np}) $$
D'après la condition (2) de la définition 1, nous savons que les coordonnées de $v^+$ ne diffèrent de celles de $v$ que par l'une d'entre elles. Soit s'l'indice correspondant à cette coordonnée. Cela est aussi vrai pour $v^-$, et nous appelons e l'indice correspondant.

Si nous écrivons en base 2 les coordonnées de $u$, celui-ci peut-être désigné par $((x_{ij}^+, j=1, p+1)_{i=1,n})$.

Avec cette notation, nous aurons $v = ((x_{ij}^+, j=1,p)_{i=1,n})$.

D'après la condition (3) de la définition 1, l'image de $v$ par le balayage d'ordre $p+1$ doit être l'ensemble $\{w \in \mathcal{U}(2,1, np+n) ; w \subset \mathcal{F}(2,n,p;v)\}$.

C'est l'ensemble des $2^n$ cylindres unidimensionnels de rang $n$ ($p+1$) contenus dans l'image de $v$. En base binaire, ce sont des $n(p+1)$ - uplets de l'ensemble :

$$ \{(Z_j, j=1, n \times p+n) \text{ où } (Z_j, j=1, np) = \mathcal{F}(2, n, p; v)\} $$

Le problème se ramène donc à la recherche d'une application de $\{u \in \mathcal{U}(2,n,p+1); u \subset v\}$ dans $\{w \in \mathcal{U}(2,1, np+n) ; w \subset \mathcal{F}(2,n,p;v)\}$, ou, avec les notations binaires :
$\{(x_{ip+1}^+, i=1,n)\}$ doit être appliqué sur $\{(Z_j, j= np, np+n)\}$.

Ce problème peut être posé comme la recherche d'un balayage de Péano d'ordre 1 avec les contraintes suivantes.

Pour chaque $v \in \mathcal{U}(2,n,p)$ nous avons défini $v^+$ comme son suivant sur le balayage et $v^-$ comme le cylindre précédent.

Si nous cherchons l'ensemble des $u \subset v$ tels que $u$ et $v^+$ soient contigus, nous obtenons $\{(x_1^{p+1}, i=1,n) ; x_s^{p+1} = \beta_s\}$ où $\beta_s \in \{0,1\}$ et s est l'indice défini précédemment.

Supposons que nous ayons déjà trouvé le balayage d'ordre 1 dans $v^-$. Alors, de la case de sortie dans $v^-$ nous déduisons la case d'entrée dans $v$: seule la coordonnée d'indice e varie.

La face de sortie doit être $\{(x_{i}^{p+1}, i=1,n) ; x_{s}^{p+1} = \beta_{s}\}$.

Donc, le problème est de trouver un balayage de Péano d'ordre 1 avec une case d'entrée donnée et une face de sortie donnée. Ce balayage existe d'après l'étape 1.

Ceci montre qu'un balayage d'ordre $p+1$ existe, et est obtenu en remplaçant séquentiellement chaque cylindre du balayage d'ordre $p$ par un balayage local d'ordre 1, dont la case d'entrée est déterminée par la case de sortie du précédent balayage local, et la face de sortie par le cylindre de rang $p$ suivant.
## ETAPE 3 : L'ALGORITHME

Il est nécessaire de préciser les deux contraintes sur le balayage d'ordre 1 : la case d'entrée et la face de sortie.

Nous devons trouver la condition sur u pour que u et $v^+$, tels qu'ils ont été précédemment définis, soient connectés.

Soient $((y_{ij}, j=1,p) \ i=1,n)$ les coordonnées de $v^+$. Comme v et $v^+$ sont contigus par leur face s, il y a deux possibilités :

$$ (1) \quad \sum_{j=1}^{p} y_{sj} 2^{-j} = \sum_{j=1}^{p} x_{sj} 2^{-j} - 2^{-p} $$

$$ (2) \quad \sum_{j=1}^{p} y_{sj} 2^{-j} = \sum_{j=1}^{p} x_{sj} 2^{-j} + 2^{-p} $$

Dans le premier cas, la borne inférieure de u doit être égale à la borne supérieure de $v^+$, soit :

$$ \sum_{j=1}^{p+1} x_{sj} 2^{-j} = \sum_{j=1}^{p} y_{sj} 2^{-j} + 2^{-p} \quad (3) $$

La combinaison de (3) et (1) nous donne $x_{sp+1} = 0$ : dans ce cas, donc la grandeur $\beta_s$ précédemment définie vaut 0.

Dans le second cas, u doit vérifier :

$$ \sum_{j=1}^{p+1} x_{sj} 2^{-j} + 2^{-p-1} = \sum_{j=1}^{p} y_{sj} 2^{-j} \quad (4) $$

De (2) et (4) nous déduisons $x_{sp+1} 2^{-p-1} + 2^{-p-1} = 2^{-p}$, soit $x_{sp+1} = 1$ (donc $\beta_s = 1$).

Maintenant, définissons $k_s = \max \{k ; \exists t \in \mathcal{U}(2,n,k-1) ; v_c(t) \text{ et } v_c(t+1)\}$

$$ \text{Nous aurons : } \begin{cases} y_{sj} = x_{sj} & \text{si } j < k_s \\ y_{sj} = 1 - x_{sj} & \text{si } j > k_s \end{cases} \quad (5) $$
De (1) et (5) nous déduisons :

$$ \sum_{j=k_s}^{p} (1-x_{sj}) 2^{-j} = \sum_{j=k_s}^{p} x_{sj} 2^{-j} - 2^{-p} \quad (6) $$

La seule possibilité est $x_{sk_s} = 1$ et $x_{sj} = 0$ pour $j>k_s$. Comme il peut arriver que $k_s = p$, la meilleure manière de calculer $\beta_s$ est de poser : $\beta_s = 1-x_{sk_s}$ (7)

En combinant (2) et (5) nous voyons que (7) est aussi vrai dans le second cas.

Nous sommes maintenant en mesure, à partir de (7) et de l'étape 1 de la
demonstration, de déduire l'algorithme :

'TREE' construit les balayages de dimension $n-1$, $\phi_1$ et $\phi_2$

'SCAN' construit le balayage de dimension n, $\phi$. L'indice i, qui a une
signification particulière, est le second argument de 'SCAN'.

'FOCUS' choisit la bonne valeur de i, d'après (7).

L'algorithme donnera à l'hypercube courant, $u = ((x_{ij}, j=1,p) \quad i=1,n)$, les
valeurs successives telles que la suite des $\phi$ (u) parcoure l'intervalle $[0,1[$.

Les paramètres $e$ et $k_e$ définis dans l'algorithme sont tels que $e(v) = s(v^-)$
et $k_e(v) = k_s(v^-)$.

L'instruction $x_{ek} = 1 - x_{ek}^-$ dans 'FOCUS' est nécessaire pour incrémenter $u$
de la case de sortie de $v^-$ à la case d'entrée de $v$.

## 7. - RESULTATS-COMPLEXITE

L'algorithme que nous avons décrit dans ce rapport a d'abord été écrit en
LISP [15], pour la mise au point, puis transformé en FORTRAN. Cette dernière
version pourrait être améliorée en supprimant certaines redondances dues à son
origine LISP. Avec cette restriction, les résultats obtenus sont donnés par le
tableau 10.
<table><caption>Tableau 10.a : Résultats lorsque le seuil de 'TEST' vaut 0</caption><thead><tr><th rowspan="2">Ensemble de données</th><th rowspan="2">N</th><th rowspan="2">n</th><th rowspan="2">k<sub>max</sub></th><th rowspan="2">Temps CPU (sec)</th><th colspan="7">Nombre de cylindres engendrés</th></tr><tr><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td rowspan="4">RUSPINI [16]</td><td rowspan="4">75</td><td rowspan="4">2</td><td>4</td><td>.15</td><td>4</td><td>8</td><td>20</td><td>44</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>.21</td><td>4</td><td>8</td><td>20</td><td>44</td><td>88</td><td>-</td><td>-</td></tr><tr><td>6</td><td>.31</td><td>4</td><td>8</td><td>20</td><td>44</td><td>88</td><td>160</td><td>-</td></tr><tr><td>7</td><td>.44</td><td>4</td><td>8</td><td>20</td><td>44</td><td>88</td><td>160</td><td>260</td></tr><tr><td rowspan="3">GOVAERT [17]</td><td rowspan="3">107</td><td rowspan="3">2</td><td>3</td><td>.16</td><td>4</td><td>16</td><td>44</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>4</td><td>.24</td><td>4</td><td>16</td><td>44</td><td>84</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>.34</td><td>4</td><td>16</td><td>44</td><td>84</td><td>152</td><td>-</td><td>-</td></tr><tr><td rowspan="3">IRIS [18]</td><td rowspan="3">100</td><td rowspan="3">4</td><td>3</td><td>.44</td><td>16</td><td>32</td><td>112</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>4</td><td>.76</td><td>16</td><td>32</td><td>112</td><td>400</td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>1.46</td><td>16</td><td>32</td><td>112</td><td>400</td><td>1232</td><td>-</td><td>-</td></tr></tbody></table>

<table><caption>Tableau 10.b : Nombre de cylindres de rang k engendrés, en fonction du seuil de 'TEST' sur les données de RUSPINI (n=2, N=75, k<sub>max</sub> = 4)</caption><thead><tr><th>Seuil de 'TEST'</th><th>k=1</th><th>k=2</th><th>k=3</th><th>k=4</th></tr></thead><tbody><tr><td>0</td><td>4</td><td>8</td><td>20</td><td>44</td></tr><tr><td>1</td><td>4</td><td>8</td><td>16</td><td>32</td></tr><tr><td>2</td><td>4</td><td>4</td><td>12</td><td>24</td></tr><tr><td>3</td><td>4</td><td>4</td><td>12</td><td>24</td></tr><tr><td>4</td><td>4</td><td>4</td><td>12</td><td>24</td></tr><tr><td>5</td><td>4</td><td>4</td><td>12</td><td>20</td></tr><tr><td>6</td><td>4</td><td>4</td><td>12</td><td>16</td></tr><tr><td>7</td><td>4</td><td>4</td><td>12</td><td>16</td></tr><tr><td>8</td><td>4</td><td>4</td><td>12</td><td>16</td></tr><tr><td>9</td><td>4</td><td>4</td><td>12</td><td>12</td></tr><tr><td>10</td><td>4</td><td>4</td><td>12</td><td>12</td></tr><tr><td>15</td><td>4</td><td>4</td><td>12</td><td>4</td></tr></tbody></table>

TABLEAU 10 : RESULTATS OBTENUS SUR QUELQUES ENSEMBLES DE DONNÉES
Ces résultats mettent en évidence un aspect important de notre algorithme :
sa complexité.

Nous devons étudier celle-ci en fonction de 3 paramètres : le nombre de
points N de l'ensemble de données, la dimension de l'espace, n, et la valeur
maximum de l'ordre du balayage, $k_{max}$.

Comme nous l'avons remarqué lors de la description de l'algorithme (§4),
chaque point est soumis à une seule permutation, quand il est trouvé, par 'EXTR',
appartenant à l'hypercube courant. Donc, pour chaque valeur de l'ordre du bala-
yage, il y aura N permutations dans le pire des cas, si le balayage est construit
jusq'à l'ordre $k_{max}$, il y aura $N \times k_{max}$ permutations.

L'influence de la dimension n de l'espace est plus importante, car le nombre
maximum d'opérations pour chaque point est $2^n$ : quand le seuil de la procédure
'TEST' est 0, l'ordre sera augmenté de 1, dès qu'il y aura un point dans l'hyper-
cube courant, et cela représente la division d'un hypercube en $2^n$ hypercubes.

Donc, la complexité de notre algorithme est :

- linéaire en fonction du nombre de points N

- linéaire en fonction de l'ordre maximum $k_{max}$ du balayage.

- exponentiel ($2^n$) avec la dimension n de l'espace.

Afin de comparer les complexités des différents algorithmes, nous devons
expliciter clairement ce qu'ils font.

A partir de la représentation cartésienne à n dimensions d'un ensemble de
N points, il faut construire la suite ordonnée de ces points, représentés à une
dimension. Le fait que cette liste soit ordonnée est très important pour la
comparaison.

Nous pouvons distinguer deux types d'algorithmes parmi ceux décrits au
début de ce rapport :

a) les algorithmes ahalytiques (BUTZ, BIALLY, PATRICK) : il calculent
l'image de chaque point par le balayage. Cela nous donne une complexité linéaire
en fonction de N, $k_{max}$ et n, mais il faut les compléter par un algorithme
de tri. La complexité des algorithmes de tri est généralement $N^2$, mais elle peut-
être ramenée à N logN en utilisant plus de mémoire (4xN) [20].
b) Les algorithmes récursifs (ALEXANDROV, QUINQUETON) : ils calculent le balayage et, à chaque pas, cherchent les points qui appartiennent à l'hypercube courant. Ces algorithmes obtiennent donc directement la liste ordonnée des points. Leur complexité est donc linéaire en N. En fonction de n et $k_{max}$, elle diffère entre l'algorithme d'Alexandrov, où l'ordre du balayage est le même partout, et notre algorithme, où il est défini localement. Dans le premier cas, elle est en $2^n$ et $2^{k_{max}}$, et en $2^n$ et $k_{max}$ dans le second.

<table><caption>TABLEAU 11 : COMPARAISON DES DIFFERENTS ALGORITHMES</caption><thead><tr><th>ALGORITHME</th><th>N</th><th>n</th><th>k<sub>max</sub></th></tr></thead><tbody><tr><td>ANALYTIQUE + TRI</td><td>N<sup>2</sup> ou N LogN</td><td>n</td><td>k<sub>max</sub></td></tr><tr><td>ORDRE UNIFORME RECURSIF</td><td>N</td><td>2<sup>n</sup></td><td>k<sub>max</sub></td></tr><tr><td>ORDRE LOCAL</td><td>N</td><td>2<sup>n</sup></td><td>k<sub>max</sub></td></tr></tbody></table>
## 8. - CONCLUSION

Nous avons proposé un algorithme pour calculer l'image unidimensionnelle d'un ensemble de points dans un espace à n dimensions. Les résultats montrés concernent seulement des ensembles test. L'algorithme doit être essayé sur un gros ensemble de données (données pétrolières), avec $N = 10^4$ et $n = 7$, mais nous n'avons pas encore les résultats.

Un des principaux inconvénients de cet algorithme est sa complexité élevée en fonction de la dimension n. Cette hypothèque peut être levée en essayant de construire un balayage de dimension n à partir de plusieurs balayages de dimension plus petite. Nous poursuivons maintenant les recherches dans ce sens.

Notre algorithme a été utilisé pour la classification [21] et les résultats étaient acceptables. Nous recherchons maintenant les autres applications possibles de l'algorithme en analyse de données (entre autres sur les tests statistiques).
BIBLIOGRAPHIE

[1] 1890, PEANO, G. - "Sur une courbe, qui remplit toute une aire plane", Mathematische Annalen 36, Translated in "Selected works of G. Peano", Ed. H.C. Kenedy Toronto University press, 1972.

[2] 1891, HILBERT, D. - "Über die Stetige Abbildung einer linie any ein Flächen stuck", Mathematishe Annalen 38, pp. 459-460.

[3] 1977, MANDELBROT, B. - "Fractals, form, chance and dimension", W.H. Freeman and C°, San Francisco.

[4] 1969, BIALLY, T. - "Space filling curves : Their generation and their Application to Bandwidth Reduction", IEEE inf Theory, vol. IT15, n° 6.

[5] 1978, FLAJOLET, P. and RAMSHAW, L. - "A note on Gray code and odd - even Merge" à paraître dans SIAM Journal on Computing.

[6] 1968, BUTZ, A.R. - "Space Filling Curves and Mathematical Programming" Information and Control 12, pp. 314-330.

[7] 1969, BUTZ, A.R. - "Convergence with Hilbert's Space Filling Curve", Journal of Computer and System Sciences, 3, pp. 128-146.

[8] 1971, BUTZ, A.R. - "Alternative Algorithm for Hilbert's Space Filling Curve", IEEE Computers, April 1971.

[9] 1965, KANAL, L.N., HARLEY, T.J, and ABEND, K. - "Classification of Binary Random Patterns" IEEE Inf Theory, Vol. IT11, n° 4.

[10] 1977, TOUSSAINT, G.T. - "Classifier Structure Design with Binary Valued Features", in Pattern Recognition II, Mac Gill University, MONTREAL.

[11] 1968, PATRICK, E.A., ANDERSON, D.R., BECHTEL, F.K. - "Mapping Multidimensional Space to One Dimension for Computer Output Display", IEEE Computers, Vol. C17, n° 10.
[12] 1978, ALEXANDROV, V.V., POLYAKOV, A.D., LATCHINOV, V.M., - "Synthèse et application d'analogue multidimensionnel d'une courbe de Péano", Congrès AFCET-IRIA, Reconnaissance des formes et traitement des images, Paris, Février.

[13] 1978, SIMON, J.C., et QUINQUETON, J. - "Une méthode de classification basée sur un balayage multidimensionnel de Péano", Compte rendu à l'académie des Sciences, vol. 286, p. 655.

[14] 1978, STEVENS, R.J., and LEHAR. A.F., - "Peano Curve Scanning for Automatic Shape Detection", unpublished paper.

[15] 1976, BERTHOD, M. - "FORLISP 1 : Un Lisp Hyperportable", Rapport de recherche n° 174, IRIA-LABORIA, Juin.

[16] 1972, DIDAY, E. - "Optimisation en classification automatique et reconnaissance des formes", RAIRO vol. 3, pp. 61-96.

[17] 1975, GOVAERT, G. - "Classification Automatique et Distances Adaptatives" Thèse de 3° cycle, Mathématique appliquées, Université Paris VI.

[18] 1936, FISHER, R.A. - "The use of Multiple Measurements in Taxonomic Problems", Ann Eugenics, Vol. 7, pp. 178-188.

[19] 1974, HAWKES, J. - "Haussdoff Measure, Entropy and the Independance of Small Sets". Proceeding of the London Mathematical Society (3) 28, pp. 700 à 724.

[20] 1971, LOUIT, G. - "Algorithmes de tri", DUNOD Ed.

[21] 1978, QUINQUETON, J. - "A New clustering Method Using a Peano Scanning", IJCPR IV, Kyoto, pp. 292-295.
ANNEXE 1 : VERSION LISP DU PROGRAMME 'EXTR'

EXTR

(LAMBDA NIL
(SETQ LS NIL)
(SETQ LC NIL)
(MAPC
LI
(QUØTE (LAMBDA (J)
(PRØG NIL
(DØ I 1 N 1 (OR
(AND
(GT (PT IJ) (MINI))
(LE (PT IJ) (MAX I))
(RETURN (SETQ LC (CONS J LC )))))))
(SETQ LS (CONS J LS)))))
(SETQ LI LC)
LS)
ANNEXE 2 : VERSION FORTRAN DU PROGRAMME 'EXTR'

SUBROUTINE EXTR
COMMON/PARAM/KMAX,K.KSUP,NSLIL,IZT.IZ.KE,IE.IPMAX.N,NBR
COMMON/POINTS/PT(10,1000),IPM(10)
COMMON/LISTE/LIST(1000)
COMMON/PILE1/JDEB(20),JFIN(20),IPIL1
INTEGER PT
IF(IPIL1.LE.0) GOTO 5
JDEBS=JDEB(IPIL1)
JDEBC=JDEB
JFIN=CJFIN(IPIL1)
IF(JFIN(IPIL1).LT.JDEB(IPIL1)) GOTO 4
DO 1 J=JDEBC,JFIN
DO 2 I=1,N
IF(PT(I,LIST(J)).LE.MIMIN(I)) GOTO 1
IF(PT(I,LIST(J)).GT.MAMAX(I)) GOTO 1
CONTINUE
2
C...... LE POINT CONVIENT ..........
18. IF(J.LE.JDEBS) GOTO 3
19. LLL=LIST(J)
20. LIST(J)=LIST(JDEBS)
21. LIST(JDEBS)=LLL
22. JDEBS=JDEB+1
23. 1 CONTINUE
24. C...... RETOUR VERS LE PP ..........
25. JDEB(IPIL1)=JDEBS
26. IPIL1=IPIL1+1
27. IF(IPIL1.GT.IPMAX) GOTO 5
28. JDEB(IPIL1)=JDEBC
29. JFIN(IPIL1)=JDEBS-1
30. RETURN
31. C...... LA LISTE DE DEPART EST VIDE ..........
32. 4 IPIL1=IPIL1+1
33. IF(IPIL1.GT.IPMAX) GOTO 5
34. JDEB(IPIL1)=JDEBC
35. JFIN(IPIL1)=JFINC
36. RETURN
37. C...... LA FILE EST PLEINE OU VIDE ..........
38. 5 WRITE(108,100) IPMAX,IPIL1
39. RETURN
40. 100 FORMAT(1X,16HPILE 1 SATURÉE : ,218)
41. END