On Semi-discrete Monge Kantorovich and generalized partitions

Abstract

Let $X$ a probability measure space and ${\psi }_1....{\psi }_N$ measurable, real valued functions on $X$. Consider all possible partitions of $X$ into $N$ disjoint subdomains $X_i$ on which ${\int }_{X_i}{\psi }_i$ are prescribed. We address the question of characterizing the set $(m_1,,,m_N)\in {\mathbb{R}}^N$ for which there exists a partition $X_1,...X_N$ of $X$ satisfying ${\int }_{X_i}{\psi }_i=m_i$ and discuss some optimization problems on this set of partitions. The relation of this problem to semi-discrete version of optimal mass transportation is discussed as well.

27 pages