Minkowski-type theorems and least-squares clustering
F. Aurenhammer, F. Hoffmann, and B. Aronov
-space with the power diagram of
sites partitions a given
-point set into clusters, one cluster for each
region of the diagram. In this manner, 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
-point set into
clusters of prescribed sizes, no matter where the sites are placed. Another
consequence is that constrained least-squares assignments can be computed by
finding suitable weights for the sites. In the plane, this takes roughly
time and optimal space
, which improves on previous methods.
We further show that a constrained least-squares assignment can be computed
by solving a specially structured linear program in
leads to an algorithm for iteratively improving the weights, based on the
gradient-descent method. Besides having the obvious optimization property,
least-squares assignments are shown to be useful in solving a certain
transportation problem, and in finding a least-squares fitting of two point
sets where translation and scaling are allowed. Finally, we extend the
concept of a constrained least-squares assignment to continuous distributions
of points, thereby obtaining existence results for power diagrams with
prescribed region volumes. These results are related to Minkowski's theorem
for convex polytopes. The aforementioned iterative method for approximating
the desired power diagram applies to continuous distributions as well.
Reference: F. Aurenhammer, F. Hoffmann, and B. Aronov.
Minkowski-type theorems and least-squares clustering.
Algorithmica, 20:61-76, 1998.
[SFB Report F003-075, TU Graz, Austria, 1996].