Power图的性质及构造算法研究

点集的Power图是点集Voronoi图的推广，特别适用用来解决涉及球（圆)的几何问题，文中首先对Power图的基本性质进行了几何化的证明；之后，研究了权为负数时对Power图的影响，指出在Power图的理论中允许权为负数，从而Power图可以应用到具有负权性质的领域；最后，给出了平面点集的Power图的构造算法，该算法到用Power图与正则三角化互为对偶的原理，在点集的正则三角化的基础上构造Power图，同时给出了实例以说明算法的有效性。

Research on Properties of Power Diagram and Its Construction Algorithm

Power diagram of a weighted point set is the generalization of the Voronoi diagram of a point set. It is especially appropriate for solving the geometric problems concerning spheres(circles). This paper first gives a geometric proof of the properties of the Power diagram. And then, it studies the minus weights' influence on the Power diagram, and points out that the weights of the points can be minus in the theory of Power diagram. In this sense, the application of the Power diagram can be extended to the field containing minus weights. In the end, this paper develops an algorithm for computing the Power diagram, which is based on the principle that the Power diagram of a weighted point set is the line dual graph of the regular triangulation of it, and examples are given to illustrate its efficiency.