Center of maximum-sum matchings of bichromatic points

Abstract

Let $R$ and $B$ be two disjoint point sets in the plane with $|R|=|B|=n$. Let $\mathcal{M}=\{(r_i,b_i),i=1,2,\dots ,n\}$ be a perfect matching that matches points of $R$ with points of $B$ and maximizes ${\sum }_{i=1}^n\Vert r_i-b_i\Vert$, the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point $o$ of the plane (the center of $\mathcal{M}$) such that $\Vert r_i-o\Vert +\Vert b_i-o\Vert \le \sqrt{2}\Vert r_i-b_i\Vert$ for all $i\in \{1,2,\dots ,n\}$.