Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am given 2 sets of n 2D Points. I need to find the segment set S where each of the n segments has its start and end in the first and second set respectively. The requirement is that each point must be used only once and that the set S must be the one with the lowest number of collisions between each pair of segments.
Do you know if there is an algorithm specific for this purpose or a particular paradigm that should be followed? Thanks
The related questions in the side panel led me to Joseph O'Rourke's answer to "Constructing non intersecting segments from distinct sets of points", which says that there is a solution with zero crossings (assuming points in "general position" — more on that later).
This introduced me to the idea of "ham-sandwich cuts": given a set of red points and blue points in the plane, there is a line that splits both the set of red points and the set of blue points in half, and it can be found in linear time.
Searching for "optimal ham-sandwich cut plane" then turned up this article, which appears to solve a more generalized version of your problem: "An optimal algorithm for plane matchings in multipartite geometric graphs"
(In their version there can be more than two colours / sets of points, as long as no one set contains more than half the total number of points, and allowable segments are ones that join two points of different colours / sets)
If I'm understanding it correctly, they use a divide and conquer approach that runs in n log n time, loosely:
Find a ham sandwich cut for the input point sets.
Look at the half of each point set on one side of the cut. Segments drawn between points in this half won't cross those drawn between points in the other half, so we can consider each half as an isolated sub-problem.
Recurse on each half, finding a ham sandwich cut for each, repeatedly, until the satisfying segments are trivial.
There are nuances about how you handle more than two sets (which you don't need) and how to handle points on the cut line, which I'll confess I don't yet understand in depth, so I'll have to refer you to the paper for the full treatment.
References I've found to this problem generally assume that no three points lie on a line. If I understand correctly that's not required for the zero-crossing solution to exist, outside of pathological cases where say all points are on a line with all red points at one end and blue points at the other. But it might be required for the algorithm to be guaranteed to find it or execute within the given time bounds. I am new to this topic though so I may be missing something obvious.
