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[1],[2],[3],[4].
Définition
modifier
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 d2 − r2. 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 (Ci) est une partition du plan en n régions Ri (appelés cellules), tels qu'un point P appartient à Ri si la puissance de P par rapport à Ci est plus petite que les puissances par rapport aux autres cercles[2],[3],[4].
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 Ri est un polygone convexe, l'intersection des demi-espaces bornés par l'axe radical de Ci 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].
Propriétés
modifierUn 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[3].
Constructions liées
modifierLe 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].
Algorithmes et applications
modifierLes 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é 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].
Historique
modifierAurenhammer 1987 retrace la définition du diagramme de Laguerre jusqu'aux travaux des mathématiciens du XIXe 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].
Notes et références
modifier- (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).
- (de) J. Linhart, « Dirichletsche Zellenkomplexe mit maximaler Eckenzahl », Geometriae Dedicata, vol. 11, no 3, , p. 363–367 (DOI 10.1007/BF00149360
, MR 627538).
- (en) Hiroshi Imai, Masao Iri et Kazuo Murota, « Voronoĭ diagram in the Laguerre geometry and its applications », SIAM Journal on Computing, vol. 14, no 1, , p. 93–105 (DOI 10.1137/0214006, MR 774929).
- (en) F. Aurenhammer, « Power diagrams: properties, algorithms and applications », SIAM Journal on Computing, vol. 16, no 1, , p. 78–96 (DOI 10.1137/0216006, MR 873251).
- (en) Herbert Edelsbrunner, « Algorithms in Combinatorial Geometry », Theoretical Computer Science, Springer-Verlag, vol. 10, , p. 327–328.
- Peter F. Ash et Ethan D. Bolker, « Generalized Dirichlet tessellations », Geometriae Dedicata, vol. 20, no 2, , p. 209–243 (DOI 10.1007/BF00164401 , MR 833848).
- David Avis, Binay K. Bhattacharya et Hiroshi Imai, « Computing the volume of the union of spheres », The Visual Computer, vol. 3, no 6, , p. 323–328 (DOI 10.1007/BF01901190 , lire en ligne).
- (en) Leonidas Guibas et Li Zhang, « Euclidean proximity and power diagrams », 10th Canadian Conference on Computational Geometry, (lire en ligne).
- (en) L. Fejes Tóth, « Illumination of convex discs », Acta Mathematica Academiae Scientiarum Hungaricae, vol. 29, nos 3-4, , p. 355–360 (DOI 10.1007/BF01895856 , MR 0464065).
- (en) F. Aurenhammer et H. Imai, « Geometric relations among Voronoĭ diagrams », Geometriae Dedicata, vol. 27, no 1, , p. 65–75 (DOI 10.1007/BF00181613 , MR 950323).
