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.

  • 1
    $\begingroup$ This is a nice answer. The "No 3 points on a line" is what is known as a "general position" assumption. These assumptions are usually made because they 1. vastly simplify algorithm descriptions 2. Are easy to deal with in practice, as they either vanish due to inherent input imprecision, or can be handled by randomization/approximation techniques or symbolic perturbation. The textbook "Computational Geometry" (by the "3 Mar(c)ks" (you may have heard about Mark Overmars) and Otfried Cheong) has a good (though brief) discussion in chapter 1. $\endgroup$
    – Discrete lizard
    Oct 14 at 16:52
  • 1
    $\begingroup$ Of course, there are cases (though rare) where you really want to deal with 3 points (or more) on a line. In those cases, you will need to decide what to do. I think here, what would probably work is pretend some of the points are an infinitesimal distance above the line (a bit like symbolic perturbation) for most of the algorithm, and deal with the case where the line is chosen as a special case. Usually, these special cases are a piece of work, but generally easier if you know the precise application, so we "Algorithm designers" leave this to the "Algorithm engineers". $\endgroup$
    – Discrete lizard
    Oct 14 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.