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 ⌊n/2⌋. Given a color-balanced point set P, a balanced cut is a line which partitions P into two colorbalanced 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 Θ(n log n) time.
Biniaz, A. (Ahmad), Maheshwari, A, Nandy, S.C. (Subhas C.), & Smid, M. (2015). An optimal algorithm for plane matchings in multipartite geometric graphs. doi:10.1007/978-3-319-21840-3_6