Diagramme de Laguerre
# Diagramme de Laguerre

En géométrie algorithmique, un diagramme de Laguerre, aussi appelé diagramme de puissance, diagramme de Laguerre–Voronoi, complexe de cellules de Dirichlet, tesselation radicale de Voronoi ou tesselation sectionnelle de Dirichlet, est une partition du plan euclidien en cellules polygonales défini à partir d'un ensemble de cercles. La cellule liée à un cercle C donné consiste en tous les points pour lesquels la puissance par rapport à C est inférieure à la puissance des points par rapport aux autres cercles. Le diagramme de Laguerre est une forme de diagramme de Voronoï généralisé et coïncide avec le diagramme de Voronoi des centres des cercles dans le cas où tous les cercles sont de même $rayon^,^,^,.$

## Définition

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^2$ − $r^2.$ 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^,^,.$

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^,^,.$

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^,^,.$

### Propriétés

Un diagramme de Laguerre partage de nombreuses propriétés avec celui de Voronoï, comme de n'être composé que de polytopes convexes (éventuellement non borné) ou vides. Parmi les différences majeures, on peut remarquer que le centre du cercle lié à une cellule ne trouve pas nécessairement à l'intérieur de la cellule.

## Constructions liées

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^,.$

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.

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.

## Algorithmes et applications

Les diagrammes de Laguerre du plan peuvent être construits par un algorithme de complexité en temps en O(n log $n)^,.$ 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é $O(n^{\lceil d/2\rceil })$ en temps.

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.

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

## Historique

Aurenhammer 1987 retrace la définition du diagramme de Laguerre jusqu'aux travaux des mathématiciens du XIXe siècle Edmond Laguerre et Gueorgui Voronoï. 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. 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".

