In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from a set of circles. The cell for a given circle C consists of all the points for which the power distance to C is smaller than the power distance to the other circles. The power diagram is a form of generalized Voronoi diagram, and coincides with the Voronoi diagram of the circle centers in the case that all the circles have equal radii.[1][2][3][4]
- ^ Linhart, J. (1981), "Dirichletsche Zellenkomplexe mit maximaler Eckenzahl", Geometriae Dedicata, 11 (3): 363–367, doi:10.1007/BF00149360, MR 0627538, S2CID 120072781.
- ^ Imai, Hiroshi; Iri, Masao; Murota, Kazuo (1985), "Voronoĭ diagram in the Laguerre geometry and its applications", SIAM Journal on Computing, 14 (1): 93–105, doi:10.1137/0214006, MR 0774929.
- ^ Aurenhammer, F. (1987), "Power diagrams: properties, algorithms and applications", SIAM Journal on Computing, 16 (1): 78–96, doi:10.1137/0216006, MR 0873251.
- ^ Edelsbrunner, Herbert (1987), "13.6 Power Diagrams", Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, pp. 327–328.