I wanted to know an efficient algorithm to match (partition into n/2 distinct pairs) n=2k points in general position in the plane in such way that segments joining the matched points do not cross. Any idea would help out immmensely.
1
-
11 questions asked and no votes?j_random_hacker– j_random_hacker2015-04-28 16:06:54 +00:00Commented Apr 28, 2015 at 16:06
Add a comment
|
2 Answers
Mr. SRKV there is a simpler way of doing it.
- Sort all the points based on the x-coordinate.
- Now pair the left most point with the next left most one.
- Remove the two points that we just paired.
- Continue from Step 2 till there are no points left.
In case two points have the same x-coordinate. The following is the tie breaking rule.
- Join the point with the lower y-coordinate to the point with the 2nd lowest y-coordinate.
- If there are an odd number of points with the same x-coordinate, then we join the lone remaining point (topmost y) with the next x-coordinate(if multiple then the lowest one).
Total complexity O(nlogn) to sort and O(n) to traverse so asymptotically it is O(nlogn).
Comments
- Find the convex hull.
- Working your way around the hull (let's say clockwise), take adjacent pairs of vertices and add them to your set of pairs. Delete each pair from the graph as you do so. If the hull contains an even number of points, then all of them will be deleted, otherwise 1 will be left over.
- If the graph still contains points, goto 1.
If each hull contains an even number of points, then it's clear that every pair of line segments found by this algorithm either came from the same hull, or from different hulls -- and either way, they will not intersect. I'm convinced it will work even when some hulls have an odd number of points.
answered Apr 25, 2015 at 19:43
j_random_hacker
51.6k10 gold badges109 silver badges176 bronze badges
2 Comments
SRKV
Thanks for your thoughts here. I had a question to add here.As above, but if we have k points that are red and if other k are blue.Can we use ham-sandwich theoram to match reds to blues so that line segments joining the matched points do not cross. What could be an efficient algorithm that could be used and what will be its complexity ? (K is a power of 2)
j_random_hacker
I haven't heard of that theorem, but the Wikipedia page says that there's an O(n) algorithm by Lo and Steiger for finding a line that cuts the plane into 2 sections, each having half the red and half the blue points. So if K is a power of 2, this will necessarily result in a k base case plane regions, each containing 1 red and 1 blue point. Since the regions are disjoint and each line segment is contained with a single region, none of the line segments can intersect.