Consider a circle of unit circumference. Suppose that there are r equidistant red points on the circle. We will drop b>r blue points on the circle. The location of each blue point is iid and uniformly distributed on the circle.

We will match red and blue points so that each red point is matched to exactly one blue point, and each blue point is matched to at most one red. Consider one of the following matching processes:

- Pick a red point uniformly at random and match it to the closest blue point. Remove the matched points. Iterate until all red points are matched.
- Match blue and red points such that the total distance achieved by the matching is minimized.

Let $X_i$ denote the distance between the $i$th red point, and the blue point it is matched to. What are $\mathbb{E}[X_i]$ and $\mathbb{E}[X_i^2]$? How do they scale with $b$ and $r$?

Finally, suppose that as opposed to unit circle, we have unit disc or square. How do these quantities change?

EDIT: If it simplifies analysis, in matching process 1, it is fine to assume that each red point is matched to the blue point that is closest, in the clock-wise direction.

2more comments