An algorithm presented by Prof. Ran Libeskind-Hadas in HMC CS 140, Spring 2013.
Don’t cross the streams.
Why?
It would be bad.
I’m fuzzy on the whole good/bad thing. What do you mean, “bad”?
Try to imagine all life as you know it stopping instantaneously and every molecule in your body exploding at the speed of light.
Total protonic reversal.
Right. That’s bad. Okay. All right. Important safety tip. Thanks, Egon.
—Ghostbusters
Given n ghosts and n ghostbusters in the plane, the goal is to match them up so that all ghosts can be busted without crossing the streams! This algorithm works by repeatedly matching ghosts & ghostbusters on the convex hull of the unmatched points (using the Graham scan algorithm) — since any matchings that can be made on the convex hull are guaranteed not to cross any others. If the convex hull contains only ghosts or only ghostbusters, the problem is divided into two subproblems, each having the same number of ghosts as ghostbusters.
Enable JavaScript!