Construction de la mosaïque de Voronoï

Plaçons-nous dans un carré (disons de côté 1), et prenons deux points, $A$ et $B$, dans ce dernier, comme dans la figure ci-dessous.
Nous y avons également tracé, en rouge, la portion de la médiatrice qui se situe dans le carré. C’est en fait le lieu où l’on est aussi proche de $A$ que de $B$. La figure suivante est un peu plus précise : elle fait apparaître en vert le lieu où l’on est plus proche de $A$ que de $B$ ; et en bleu le cas opposé. Un point est plus proche de A ou de B selon qu’il se situe d’un côté ou de l’autre de la médiatrice.

Ce que nous avons fait concerne deux points. Mais, que se passe-t-il si, au lieu d’en prendre deux, on en prend trois ? Voici, par exemple, ce que l’on obtient :
Dans cette figure, nous avons pris trois points : $A$, $B$ et $C$. La partie bleue est l’endroit où l’on est plus proche de $A$ que des deux autres points ; la beige est celle où l’on est plus proche de $B$ ; et la verte celle où l’on est plus proche de $C$. Remarquons que le segment qu’il y a entre $A$ et $B$, par exemple, est une portion de la médiatrice entre ces deux points.

Allons plus loin : que se passe-t-il si on prend encore plus de points ? Disons 28. On obtient, par exemple, ceci :
En vert, se situe le lieu où l’on est plus proche du point $A$ que de tous les autres points noirs. On remarque que c’est un polygone. Ce dernier a un nom : on l’appelle la cellule de Voronoï de germe $A$. Remarquons qu’en fait on a la même chose pour tous les points noirs : pour chacun de ces points, la portion où l’on est plus proche de ce point que des autres est aussi un polygone. En fait, ce n’est guère étonnant car toutes ces portions ont été construites à partir des médiatrices des points noirs pris deux à deux. On obtient donc une famille de polygones qui forment un découpage du carré. On appelle ce découpage la mosaïque, ou le diagramme, de Voronoï. La mosaïque de Voronoï a un grand nombre d’applications dans divers domaines, notamment en télécommunications pour des modélisations de réseaux, en biologie pour modéliser des protéines, ou encore en astrophysique pour l’étude de structures spatiales des populations d’étoiles. On l’observe également dans la nature : par exemple, les taches de girafe ressemblent à des cellules de Voronoï.

À notre connaissance, cela vient du fait que les cellules productrices de mélanine, qui confèrent le caractère brun aux taches, grossissent jusqu’à rencontrer des cellules issues d’autres taches. On trouve également des cellules de Voronoï sur d’autres animaux, notamment la carapace de certaines tortues :

Pour de plus amples informations sur cette mosaïque, nous vous invitons à lire « Jouez avec les diagrammes de Voronoï ».

Des mosaïques construites au hasard

Dans ce qui suit, nous allons jouer aux probabilités avec Voronoï. Plus précisément, les points qui permettent de construire nos cellules (c’étaient les points noirs dans la figure précédente) seront pris au hasard. Par hasard, il faut comprendre que chacun de ces points a autant de chance (et ce, indépendamment des autres points) de se trouver dans n’importe quel petit carré d’un quadrillage de la figure aussi fin qu’on le fasse. Nous avons demandé à Matlab (c’est un logiciel de mathématiques) de lancer au hasard 1000 points puis de construire la mosaïque associée à ces points. Voici ce que l’on obtient.
On dit, dans un vocabulaire probabiliste, que l’on a une réalisation de la mosaïque. La figure suivante donne une autre réalisation quand on lance, encore au hasard, 1000 points, indépendamment de ce qu’on a fait précédemment.
Une troisième réalisation, toujours avec 1000 points qui ont été pris au hasard, donne ceci.
On constate que les trois mosaïques ci-dessus sont différentes : cela est dû au fait que les points qui ont permis de construire nos cellules ont été lancés au hasard.

La plus grosse cellule

Nous ne sommes intéressés que par les cellules qui ne touchent aucun des quatre côtés du carré. On dira de ces cellules qu’elles sont « à l’intérieur ». A contrario, les cellules qui touchent l’un des quatre côtés du carré (celles qui se situent donc à la frontière) ne nous intéressent pas car elles sont atypiques, peu représentatives, et de toute façon elles sont peu nombreuses par rapport aux autres. La question principale de cet article est : que peut-on dire de la cellule (à l’intérieur du carré) qui a la plus grande aire ? Si l’on reprend les figures de la section précédente, la cellule coloriée en rouge est celle qui a la plus grande aire. Que constate-t-on ? A chaque fois, la cellule rouge est assez arrondie. Elle n’est d’ailleurs pas la seule à l’être, mais nous nous concentrons ici sur l’étude de cette plus grande cellule.

Regardons ce qu’il se passe lorsque le nombre de points lancés est plus grand. Pour cela, nous avons demandé à Matlab de prendre un million de points au hasard, de tracer la mosaïque, et de nous dire quelle est la plus grande cellule. Puis, nous avons refait la même chose une deuxième fois, et une troisième fois, en prenant à nouveau un million de points au hasard. Nous obtenons donc trois mosaïques. Nous ne les avons pas représentées car les cellules sont toutes petites. La figure ci-dessous représente la plus grosse cellule (celle qui a la plus grande aire) pour chacune d’entre elles. Nous avons fait un zoom, en précisant l’échelle, pour bien voir à quoi elle ressemble (le germe de chaque cellule est représenté par un point noir). Remarquons au passage que l’aire de chaque cellule est (un peu) plus grande que $10^{-6}$, c’est-à-dire un millionième. Ce n’est guère étonnant. En effet, on sait qu’il y a, à chaque fois, un million de cellules dans un carré dont l’aire est égale à 1. Donc l’aire d’une cellule prise au hasard est d’environ un millionième, et la cellule qui a la plus grande aire a nécessairement une aire supérieure à cette valeur. On constate également que les trois cellules sont assez arrondies. En fait, on est dans le cœur d’une conjecture due à Kendall que nous énonçons comme suit.

Cette conjecture signifie que si nous lançons beaucoup de points au hasard, la plupart du temps, la plus grosse cellule ressemblera à un disque, et sera donc arrondie. Elle ne veut pas dire pour autant qu’on est toujours sûr qu’elle sera arrondie : un scénario où la cellule n’est pas du tout circulaire peut se produire, par exemple si c’est un triangle allongé, mais très rarement ; et d’autant plus rarement que le nombre de points qu’on a lancés est grand.

Nous avons intitulé notre article, ainsi que l’énoncé ci-dessus, « une version de la conjecture de Kendall » car il ne s’agit pas de la version originale, telle qu’elle a été réellement énoncée par D. G. Kendall dans les années 40. Cette conjecture a été en fait émise dans un autre contexte (voir l’avant-propos de la première édition de [SKM95]). Nous avons préféré donner une version modifiée de sa conjecture car nous pensons qu’elle est plus compréhensible. Pour une biographie de D. G. Kendall, nous renvoyons le lecteur à wikipedia.

La conjecture originale de Kendall a été résolue par I. N. Kovalenko en 1997 (voir Ko99 pour une preuve). La version que nous avons énoncée a été résolue, dans un contexte légèrement différent, par trois mathématiciens allemands : D. Hug, M. Reitzner et R. Schneider en 2004 (Théorème 1 de HRZ). Voici une adaptation de leur résultat.

Afin de bien comprendre le théorème, regardons la figure suivante.
Elle fait apparaître une cellule de Voronoï (en vert) et son germe $A$. Dans cette figure, le cercle bleu délimite le plus grand disque, centré en $A$, qui est contenu dans la cellule tandis que le cercle rouge délimite le plus petit disque, centré en $A$, qui contient la cellule. Bien entendu, le rayon $r(C)$ du cercle bleu est toujours plus petit que le rayon $R(C)$ du cercle rouge. Ce que dit le théorème, c’est que lorsqu’on lance un grand nombre de points et qu’on prend la plus grande cellule, le plus souvent, ces deux rayons sont très proches (dans le sens où le quotient $r(C)/R(C)$ est proche de 1). Cela répond bien à la conjecture 1 car dire que les cercles bleu et rouge sont presque identiques signifie que la cellule est presque un disque.

Si l’on reprenait la figure du début de cette section et qu’on devait tracer les cercles bleus et rouges, pour chacune des trois cellules, on se rendrait compte qu’ils ne sont pas vraiment identiques. La raison est que, pour des questions techniques, nous n’avons lancé qu’un million de points pour construire chacune des trois mosaïques. Il faut imaginer que si on avait pris beaucoup plus de points (mais vraiment beaucoup plus !) alors le plus souvent le cercle bleu sera presque le même que le cercle rouge. Plus précisément, la chance que le rapport des rayons $r(C)/R(C)$ soit proche de 1 est d’autant plus élevée que le nombre $n$ de points est grand. En fait, on est même capable d’avoir une idée de la chance que ce rapport soit plus grand qu’une tolérance qu’on se fixe. Par exemple, si le nombre de points $n$ possède environ 500 000 chiffres, alors on sait qu’il y a au moins 95% de chance que $r(C)/R(C)$ soit plus grand que 0.99. Il faut un peu plus d’une centaine de pages pour écrire un tel nombre $n$, et sa taille anéantit toute tentative d’imagination (par exemple, le nombre de particules dans l’Univers visible possède moins de 100 chiffres). Les ordinateurs ne seront jamais capables de construire des mosaïques avec autant de points. En pratique, on peut dire qu’on n’arrivera jamais à observer des mosaïques (aléatoires) dont la plus grande cellule est très proche d’un cercle (c’est le cas, par exemple, si $r(C)/R(C)$ est plus grand que 0.99) ; et pourtant, en théorie, on sait que cela est vrai lorsque le nombre de points $n$ est très grand. L’une des beautés des mathématiques est de savoir qu’un résultat est vrai alors qu’on n’est pas capable de l’observer.

La conjecture de Kendall a débouché sur un grand nombre de questions. En voici quelques unes. Est-ce que ce résultat est encore vrai si on considère non pas la cellule qui a la plus grande aire, mais celle qui a le plus grand périmètre ou celle qui a le plus grand nombre de sommets ? C’est une question différente car il n’y a pas de raison que la cellule qui a la plus grande aire soit la même que celle qui a le plus grand périmètre, ou le plus grand nombre de sommets. Que se passe-t-il si à la place de considérer une mosaïque dans le carré, on considère une mosaïque dans un cube ? Que se passe-t-il si l’on considère d’autres types de mosaïques ? Plusieurs de ces questions ont déjà été résolues entre 2000 et 2010. Il s’avère que, suivant ce que l’on entend par « grosse » cellule (cela peut être celle qui a la plus grande aire, celle qui a le plus grand périmètre, ou encore celle qui a le plus grand nombre de sommets), la réponse est généralement la même : une grosse cellule est presque toujours arrondie quand on lance beaucoup de points.

La plus petite cellule

Il reste encore de nombreuses questions ouvertes et qui constituent une part active de la recherche en géométrie aléatoire. On sait donc à quoi ressemblent les grosses cellules ; en revanche peu de choses ont été faites sur les petites cellules. À quoi ressemblent-elles ? Pour voir cela de plus près, nous avons construit une mosaïque de Voronoï avec un million de points lancés au hasard et observé la cellule qui a la plus petite aire ; puis nous avons fait cela, une deuxième, une troisième fois. À nouveau, nous n’avons pas représenté les mosaïques. La figure suivante montre à quoi ressemble la cellule qui a la plus petite aire pour chacune de ces trois mosaïques. Il semble, au vu de ces figures, que la cellule la plus petite est souvent un triangle. Mais, ce n’est pas très convaincant car nous n’avons que trois mosaïques

Pour avoir une idée plus précise de ce à quoi ressemble une petite cellule, nous avons fait la même chose que ci-dessus, cette fois-ci non pas avec trois mosaïques mais avec cent mosaïques. Plus précisément, nous avons lancé un million de points au hasard pour construire une mosaïque ; et nous avons réitéré l’expérience pour avoir un total de cent mosaïques. Nous avons compté le nombre d’entre elles pour lesquelles la plus petite cellule est un triangle (trois sommets), un quadrilatère (quatre sommets), un pentagone (cinq sommets). Les résultats sont donnés dans le tableau ci-dessous.

Dans ce tableau, on peut constater que sur les 100 mosaïques, il y en a 85 dont la plus petite cellule est un triangle et 15 dont la plus petite est un quadrilatère. Il n’y a eu aucun cas où la plus petite cellule avait au moins 5 sommets. Cela ne signifie pas qu’il est impossible que la plus petite cellule ait au moins 5 sommets : peut-être que nous n’avons pas eu de chance avec nos mosaïques. Sans doute que si nous avions fait énormément de mosaïques, nous serions tombés sur un cas où la plus petite cellule est un pentagone ; mais cela est sans doute extrêmement rare par rapport au nombre de fois où l’on va avoir un triangle ou un quadrilatère.

Il n’est pas clair que la plus petite cellule est, la quasi-totalité du temps, un triangle : 15 d’entre elles, en effet, ne sont pas des triangles, ce qui est quand même non négligeable. Peut-être que si nous lancions plus de points, nous en saurions davantage ; et peut-être que nous constaterions, dans ce cas, que la plupart du temps la plus petite cellule est un triangle. Mais construire une mosaïque avec beaucoup de points (par exemple 1000 milliards) demande beaucoup de temps à l’ordinateur, et d’ailleurs les ordinateurs ne sont pas suffisamment performants pour faire cela. En consultant le tableau, nous avons cependant envie d’émettre la conjecture suivante.

À la différence de la première conjecture, celle qui apparaît ci-dessus est une question ouverte. Aujourd’hui, on ne sait pas si ce résultat est vrai.