Diagrammes de Voronoi

Diagrammes de Voronoi

Vincent Pilaud

2006

1. Introduction

Soit n un entier, E un espace euclidien de dimension n, S un ensemble fini de points de E et P ∈ S. On appelle cellule de Voronoi de P (dans S) l’ensemble des points de E situ´es plus pr`es de P que de tous les autres points de S :

VorS(P) = {M ∈ E | ∀ Q ∈ S, MP ≤ MQ}.

On appelle diagramme de Voronoi de S le diagramme form´e de l’ensemble des cellules de Voronoi des points de S :

Vor(S) = {VorS(P) | P ∈ S}.

Les diagrammes de Voronoi apparaissent naturellement dans diff´erentes situations :

• probl`emes de r´epartition : les habitants d’une ville se rendant toujours au bureau de poste le plus proche de chezeux, la r´epartition des utilisateurs des bureaux de poste suit un diagramme de Voronoi. Il est par cons´equent int´eressant d’´etudier de tels diagrammes lorsque l’on veut choisir l’emplacement d’un nouveau bureau.

[pic 1]

Fig. 1 – Diagramme de Voronoi et coˆnes d’influence

• probl`emes de croissance : lorsqu’on dispose des ´echantillons de bact´eries sur une planche nutritive, on observe unecroissance centrifuge qui s’arr`ete lorsque deux ´echantillons se rejoignent. Si toutes les bact´eries se d´eveloppent `a la mˆeme vitesse, on obtient ainsi le diagramme de Voronoi des points correspondant `a l’emplacement initial des ´echantillons (fig. 1). On observe le mˆeme ph´enom`ene sur la carapace des tortues ou dans le cou des girafes r´eticul´es (fig. 2).

Fig. 2 – Giraphe r´eticul´ee et tortue

Dans ce texte, on pr´esente plusieurs aspects des diagrammes de Voronoi. On ´etudie d’abord l’espace des sph`eres de E, les faisceaux de sph`eres et la repr`esentation d’un diagramme de Voronoi comme projection de l’intersection de certains demi-espaces de l’espace des sph`eres (th´eor`eme 1). On propose ensuite un algorithme de calcul de diagrammes de Voronoi plans par une technique de balayage. On pr´esente enfin un r´esultat de projection pour les diagrammes de Voronoi de l’espace hyperbolique (th´eor`eme 2), analogue au r´esultat du cadre euclidien de la partie 2.

1. L’espace des sph`eres

1. D´efinitions

Soient P ∈ E et R ∈ R+. On appelle puissance de la sph`ere de centre P et de rayon R l’application ΣP,R de E dans R qui `a un point M associe ΣP,R(M) = MP2 − R2. La puissance d’une sph`ere est clairement nulle sur cette sph`ere, positive `a l’ext´erieur et n´egative `a l’int´erieur. Elle atteind son minimum au centre de la sph`ere. Le centre et le rayon de la sph`ere sont donc d´etermin´es par la puissance de la sph`ere. Dans la suite, on confond une sph`ere et sa puissance.

A la sph`ere Σ` P,R de E de centre P et de rayon R, on fait correspondre le point Ψ(ΣP,R) = (P,P2 − R2) ∈ E × R. L’ensemble E˜ = E × R est appell´e espace des sph`eres. On notera x la premi`ere coordonn´ee des points de cet espace (x ∈ E) et t la deuxi`eme (t ∈ R); on parlera d’abscisse et d’ordonn´ee. Le parabolo¨ıde P de E˜ d’´equation t = x2 repr´esente les sph`eres de rayon nul. Tous les points de E˜ situ´es au-dessous de P correspondent aux sph`eres r´eelles de E tandis que les points de E˜ au-dessus de P sont des sph`eres imaginaires.

Nous allons voir dans ce qui suit que les probl`emes relatifs aux sph`eres dans l’espace E peuvent se voir comme des probl`emes lin´eaires dans l’espace des sph`eres E˜. On a ainsi lin´earis´e ces probl`emes en augmentant la dimension de l’espace. Pour illustrer ceci, on commence par ´etudier les faisceaux de sph`eres de E, puis on applique cette lin´earisation aux diagrammes de Voronoi.

1. Faisceaux de sph`eres

Un faisceau de sph`eres est l’ensemble FΣ1,Σ2 des sph`eres combinaisons lin´eaires affines de deux sph`eres donn´ees

Σ1 et Σ2 :

FΣ1,Σ2 = {λΣ1 + (1 − λ)Σ2 | λ ∈ R}, (ou` λΣ1 + (1 − λ)Σ2 d´esigne la sph`ere de puissance M 7→ λΣ1(M) + (1 − λ)Σ2(M)).

On v´erifie que le faisceau de sph`eres FΣ1,Σ2 est envoy´e par Ψ dans l’espace des sph`eres sur une droite passant par les points de Ψ(Σ1) et Ψ(Σ2). Les faisceaux de sph`eres peuvent donc se classer suivant le nombre d’intersections de leur image par Ψ avec le parabolo¨ıde P. On a ainsi les quatre situations suivantes (fig. 3) :

[pic 2]

Fig. 3 – Les quatre types de faisceaux de sph`eres

1. Si la droite Ψ(F) rencontre P en deux points, F contient deux sph`eres de rayon nul que l’on appelle points limites du faisceau F.
2. Si la droite Ψ(F) rencontre P transversalement en un point, elle est n´ecessairement verticale (puisque le parabolo¨ıde est dirig´e par la verticale). F est donc un faisceau de sph`eres concentriques.
3. Si la droite Ψ(F) ne rencontre pas P, il existe une famille d’hyperplans tangents au parabolo¨ıde P qui contiennent Ψ(F). On note ΣF l’ensemble des points de E (consid´er´es comme des sph`eres de rayon nul) qui appartiennent `a toutes les sph`eres du faisceau F. L’image par Ψ de ΣF correspond aux points de contact avec P des hyperplans tangents `a P et contenant Ψ(F). Ainsi, ΣF est non vide, et on v´erifie que c’est une sph`ere de dimension n − 1 que l’on appelle sph`ere de base du faisceau F.
4. Si la droite Ψ(F) est tangente `a P, on se trouve dans la situation d’un faisceau `a points limites dont les deux points limites sont confondus, ou dans celle d’un faisceau a` sph`ere de base dont la sph`ere de base est r´eduite `a un point. On parle de faisceau tangent.

1. Diagramme de Voronoi et projection

Consid´erons un point P de E (encore une fois confondu avec la sph`ere de rayon nulle correspondante), et notons HP l’hyperplan tangent au parabolo¨ıde P au point Ψ(P). L’´equation de HP est donn´e par :

t = 2hx | Pi − P2.

Par cons´equent, si P et Q sont deux points fix´es de E, un point M de E est plus proche de P que de Q si et seulement si au point d’abscisse M, l’hyperplan HP est au-dessus de l’hyperplan HQ. On en d´eduit le th´eor`eme suivant (fig. 4) :

Th´eor`eme 1. Le diagramme de Voronoi d’un ensemble fini S de points de E est obtenu par projection verticale sur E de l’intersection des demi-espaces sup´erieurs de E˜ d´elimit´es par les hyperplans HP, P ∈ S.