Don't Intersect Please :D
 Thamim Zahin
 Posts: 98
 Joined: Wed Aug 03, 2016 5:42 pm
Don't Intersect Please :D
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.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
 ahmedittihad
 Posts: 161
 Joined: Mon Mar 28, 2016 6:21 pm
Re: Don't Intersect Please :D
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.
Frankly, my dear, I don't give a damn.
 Thamim Zahin
 Posts: 98
 Joined: Wed Aug 03, 2016 5:42 pm
Re: Don't Intersect Please :D
Simple polygon will also do the trick. Isn't? If we put a super big rubberband, it will result us a simple polygon.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.

 Posts: 61
 Joined: Tue Dec 08, 2015 4:25 pm
 Location: Bashaboo , Dhaka
Re: Don't Intersect Please :D
Actually,@thamimzahin,the idea which you have is the main concept of convex hull.
http://mathworld.wolfram.com/ConvexHull.html
http://mathworld.wolfram.com/ConvexHull.html
Last edited by Absur Khan Siam on Mon Mar 06, 2017 4:46 pm, edited 1 time in total.
 ahmedittihad
 Posts: 161
 Joined: Mon Mar 28, 2016 6:21 pm
Re: Don't Intersect Please :D
@thamimzahin I seem to remember to have taught you the concept of a convex hull. Did you forget already?
Frankly, my dear, I don't give a damn.

 Posts: 61
 Joined: Tue Dec 08, 2015 4:25 pm
 Location: Bashaboo , Dhaka
Re: Don't Intersect Please :D
I think 70% or more are introduced to convex hull by this 'rubberband' concept.
 ahmedittihad
 Posts: 161
 Joined: Mon Mar 28, 2016 6:21 pm
Re: Don't Intersect Please :D
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
nonintersecting.
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
nonintersecting.
Frankly, my dear, I don't give a damn.
 Thanic Nur Samin
 Posts: 176
 Joined: Sun Dec 01, 2013 11:02 am
Re: Don't Intersect Please :D
Here is my take.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.
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.
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.