Diagramme de Laguerre

Puissance d'un point P à l'extérieur d'un cercle donné

Si C est un cercle et P un point à l'extérieur de C, alors la puissance de P par rapport à C vaut le carré de la distance entre le point P à un point T de tangence avec C. De manière équivalente, si P est à une d du centre du cercle, dont le rayon vaut r, alors (par le théorème de Pythagore) la puissance vaut d² − r². La même formule peut alors être étendue à tous les points du plan, notamment ceux qui sont à l'intérieur du cercle : les points sur le cercle C ont une puissance nulle, et ceux à l'intérieur strict de C ont une puissance négative[2] - [3] - [4].

Le diagramme de Laguerre d'un ensemble de n cercles (C_i) est une partition du plan en n régions R_i (appelés cellules), tels qu'un point P appartient à R_i si la puissance de P par rapport à C_i est plus petite que les puissances par rapport aux autres cercles[2] - [3] - [4].

L'axe radical de deux cercles concourants. Le diagramme de Laguerre de deux cercles est la partition du plan en deux demi-plans délimités par cette droite.

Dans le cas n = 2, le diagramme de Laguerre se résume à deux demi-plans, séparés par l'axe radical des deux cercles. Cet axe est l'ensemble des points ayant une puissance égale par rapport aux deux cercles. Plus généralement, dans tout diagramme de Laguerre, chaque cellule R_i est un polygone convexe, l'intersection des demi-espaces bornés par l'axe radical de C_i avec chaque autre cercle. Des triplets de cellules se retrouvent aux sommets du diagramme, qui sont les centres radicaux des trois cercles dont les cellules se rencontrent en ce sommet[2] - [3] - [4].

Le diagramme de Laguerre peut être vu comme un diagramme de Voronoï pondéré d'un ensemble de voisinages de points, uns partition du plan en cellules dans lesquelles un des voisinages est plus proche des autres sites. D'autres formes de diagrammes de Voronoï pondéré incluent le diagramme de Voronoï à poids additifs, dans lequel chaque site a un poids qui est ajouté à sa distance avant de comparer aux distances avec les autres sites, le diagramme de Voronoï à poids multiplicatifs, dans lequel chaque site a un poids qui est multiplié à sa distance avant de comparer aux distances avec les autres sites. Par contraste, dans le diagramme de Laguerre, on peut voir chaque cercle comme un site et le carré du rayon de chaque cercle comme un poids auquel on soustrait le carré de la distance euclidienne avant de le comparer aux distances élevées au carré. Dans le cas où tous les cercles ont mêmes rayons, cette soustraction ne fait aucune différence, et les diagrammes de Laguerre et de Voronoï se confondent[3] - [4].

Un diagramme de Laguerre plan peut aussi être interprété comme une section d'un diagramme de Voronoï tridimensionnel non pondéré. De ce point de vue, l'ensemble des centres des cercles du plan de section sont les projections orthogonales des sites de Voronoï tridimensionnels et le rayon élevé au carré de chaque cercle est une constante K moins la distance au carré du site correspondant depuis le plan de section, où K est choisi assez grand pour que tous les rayons soient positifs[5].

Comme un diagramme de Voronoï, la définition du diagramme de Laguerre peut être étendu aux espaces euclidiens de toute dimension. Le diagramme de Laguerre de n sphères dans un espace d-dimensionnel est combinatoirement équivalent à l'intersection d'un ensemble de n demi-espaces orientés en d + 1 dimensions, et inversement[3].

Les diagrammes de Laguerre du plan peuvent être construits par un algorithme de complexité en temps en O(n log n)[2] - [3]. De façon plus générale, à cause de l'équivalence avec des intersections de demi-plans de dimensions plus élevés, des diagrammes de Laguerre d-dimensionnels (pour d > 2) peuvent être construits par un algorithme de complexité ${\displaystyle O(n^{\lceil d/2\rceil })}$ en temps[3].

Le diagramme de Laguerre peut être utilisé dans un algorithme efficace de calcul de volume d'une union de sphères. L'intersection de chaque sphère avec sa cellule dans le diagramme de Laguerre donne sa contribution à l'union totale, de laquelle le volume peut être calculé en temps proportionnel à la complexité du diagramme de Laguerre[6].

D'autres applications sont les structures de données pour tester si un point appartient à une union de disques[2], ou la construction de la frontière d'une union de disques[2] et des algorithmes pour trouver les deux boules les plus proches dans un ensemble de boules[7].

Aurenhammer 1987 retrace la définition du diagramme de Laguerre jusqu'aux travaux des mathématiciens du XIX^e siècle Edmond Laguerre et Gueorgui Voronoï[3]. Fejes Tóth 1977 définit les diagrammes de Laguerre et les utilise pour montrer que la frontière de l'union de n disques circulaires peut toujours être illuminé par au plus 2n sources lumineuses ponctuelles[8]. Les diagrammes de Laguerre apparaissent dans la littérature sous d'autres noms comme le "diagramme de Laguerre–Voronoi", "complexe de cellules de Dirichlet", "tesselation radicale de Voronoï" et "tesselation sectionnelle de Dirichlet"[9].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Power diagram » (voir la liste des auteurs).