An Optimal Algorithm for Plane Matchings
in Multipartite Geometric Graphs
Let $P$ be a set of $n$ points in general position in the plane which is partitioned into color classes. $P$ is said to be color-balanced if the number of points of each color is at most $\lfloor n/2\rfloor$. Given a color-balanced point set $P$, a balanced cut is a line which partitions $P$ into two color-balanced point sets, each of size at most $2n/3 + 1$. A colored matching of $P$ is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. In this paper, we present an algorithm which computes a balanced cut for $P$ in linear time. Consequently, we present an algorithm which computes a plane colored matching of $P$ optimally in $\Theta(n\log n)$ time.