BdMO Online Forum

Given $2n$ points in the plane with no three collinear, show that it is possible to pair them up in such a way that the $n$ line segments joining paired points do not intersect.

Take the convex hull and select two consecutive points and pair them up. Then take the next convex hull and do the algorithm. We eventually will get what we desire.

Simple polygon will also do the trick. Isn't? If we put a super big rubber-band, it will result us a simple polygon.

Actually,@thamimzahin,the idea which you have is the main concept of convex hull.
http://mathworld.wolfram.com/ConvexHull.html

@thamimzahin I seem to remember to have taught you the concept of a convex hull. Did you forget already?

I think 70% or more are introduced to convex hull by this 'rubber-band' concept.

Related Problem,
Given $2n$ points in a plane with no three collinear, with $n$ red points and $n$ blue points, prove that
there exists a pairing of the red and blue points such that the $n$ segments joining each pair are pairwise
non-intersecting.

Thamim Zahin wrote:Given $2n$ points in the plane with no three collinear, show that it is possible to pair them up in such a way that the $n$ line segments joining paired points do not intersect.

Here is my take.

Take all possible pairings of the points, and select the one with minimum sum of the length of the segments. Due to the triangle inequality, the segments do not intersect.

The argument works in Ittihad's problem as well.