Abstract:
We consider the construction of a polyhedral Delaunay partition as a limit of the sequence of power diagrams (in Russian traditionally called radical partitions), while the dual Voronoi diagram is obtained as a limit of the sequence of weighted Delaunay partitions. Using a lifting analogy, this problem is reduced to the construction of a pair of dual convex polyhedra, inscribed and superscribed around a circular paraboloid, as a limit of the sequence of pairs of general dual convex polyhedra. The sequence of primal polyhedra should converge to the superscribed polyhedron, while the sequence of dual polyhedra converges to the inscribed polyhedron. For building sequences of dual polyhedra we are mostly interested in the case when the vertices of primal polyhedra can move or merge together. This means that no new faces are allowed for dual polyhedra. These rules essentially define the transformation of the set of initial spheres defining a power diagram into the set of Delaunay spheres using sphere movement, radius variation, and sphere elimination as admissible operations. Although a rigorous foundation (existence theorems) for this problem is still unavailable, we suggest a functional measuring the deviation of the convex polyhedron from the one inscribed into the paraboloid. This functional is the discrete Dirichlet functional for the power function (power of a point with respect to a ball) which is a linear interpolant of the vertical distance of the dual vertices from the paraboloid. The absolute minimizer of this functional is attained on the constant power field, meaning that the inscribed polyhedron can be obtained using a simple translation. This formulation of the Dirichlet functional for the dual surface is not quadratic since the unknowns are the vertices of the primal polyhedron. Hence, the transformation of the set of spheres into Delaunay spheres is not unique. In this work, we concentrate on the experimental confirmation of the viability of suggested approach and put aside mesh quality problems. The zero value of the gradient of the proposed functional defines a manifold describing the evolution of Delaunay spheres. Hence, Delaunay–Voronoi meshes can be optimized using this manifold as a constraint. Numerical examples illustrate polygonal Delaunay meshing in planar domains.
