Minkowski-type theorems and least-squares partitioning

F. Aurenhammer, F. Hoffmann, and B. Aronov


The power diagram of $n$ weighted sites partitions a given $m$-point set into clusters, one cluster for each region of the diagram. In this way, an assignment of points to sites is induced. We show the equivalence of such assignments to constrained Euclidean least-squares assignments. As a corollary, there always exists a power diagram whose regions partition a given $d$-dimensional $m$-point set into clusters of prescribed sizes, no matter where the sites are placed. Another consequence is that least-squares assignments can be computed by finding suitable weights for the sites. In the plane, this takes roughly $O(n^2m)$ time and optimal space $O(m)$, which improves on previous methods. We further show that a constrained least-squares assignment can be computed by solving a particular linear program in $n+1$ dimensions. This leads to an algorithm for iteratively improving the weights. Aside from the obvious application, least-squares assignments are shown to be useful in solving a certain transportation problem, and in finding least-squares fittings where translation and scaling are allowed. Finally, we extend the concept of a constrained least-squares assignment to continuous point sets, thereby obtaining results on power diagrams with prescribed region volumes that are related to Minkowski's theorem for convex polytopes.

Reference: F. Aurenhammer, F. Hoffmann, and B. Aronov. Minkowski-type theorems and least-squares partitioning. In Proc. $8^{th}$ Ann. ACM Symp. Computational Geometry, pages 350-357, Berlin, Germany, 1992. [Report B-92-09, FU Berlin, Germany, 1992].