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 $$

⌊

n

/

2

⌋

. 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$$

2

n

/

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)$$

Θ

(

n

log

n

)

time.