Minkowski-type theorems and least-squares partitioning
F. Aurenhammer, F. Hoffmann, and B. Aronov
The power diagram of
weighted sites partitions a given
-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
-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
time and optimal space
improves on previous methods. We further show that a constrained
least-squares assignment can be computed by solving a particular linear
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. Ann. ACM Symp. Computational Geometry, pages 350-357,
Berlin, Germany, 1992.
[Report B-92-09, FU Berlin, Germany, 1992].