Minkowski-type theorems and least-squares partitioning
Franz Aurenhammer, Friedrich Hoffman, Boris S. Aronov · 1992
The power diagram of n weighted sites in d-space partitions a given m-point s e t i n to clusters, one cluster for each region of the diagram.In this way, an assignment o f points to sites is induced.We s h o w 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 nding 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 nding least-squares ttings when translation and scaling are allowed.Finally, w e 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.