Question

A group of n Ghostbusters is battling n ghosts. Each Ghostbuster carries a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot a stream at his chosen ghost. As we all know, it is very dangerous to let streams cross, and so the Ghostbusters must choose pairings for which no streams will cross. Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and that no three positions are collinear.Give an O(n 2 lg n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross. Provide a step by step algorithm for this question.

Answer 1

Answer:

Using the above algorithm matches one pair of Ghostbuster and Ghost. On  each side of the line formed by the pairing, the number of Ghostbusters and Ghosts are  the same, so use the algorithm recursively on each side of the line to find pairings. The  worst case is when, after each iteration, one side of the line contains no Ghostbusters  or Ghosts. Then, we need n/2 total iterations to find pairings, giving us an P($n^{2} lg n$)-  time algorithm.