Minkowski-Type Theorems and Least-Squares Partitioning
Franz Aurenhammer (joint work with Boris Aronov, Friedrich Hoffmann)
Institut fü Grundlagen der
Informationsverarbeitung
Graz, Österreich
Report B 92-09
April 92
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-09.ps.gz
The power diagram of $n$ weighted sites in $d$-space
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
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 taken. 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^2 m)$ time and optimal space $O(m)$
which improves on previous methods. We further show that least-squares
assignments can be computed by solving a particular linear
program in $n+1$ dimensions. This leads to a gradient method
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 when translation and scaling are allowed.
Finally, we extend the concept of least-squares assignments to
continious point sets, thereby obtaining results on power diagrams
with prescribed region volumes that are related to Minkowski's
Theorem for convex polytopes.