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.