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

The described problem requires creating non-crossing pairings between points in a plane, utilizing a divide and conquer algorithm similar to finding the closest pair of points. The algorithm involves sorting, recursively pairing, checking for potential crossings, and merging pairs in O(n^2 lg n) time.

Step-by-step explanation:

The problem described is one of computational geometry, specifically related to the pairing of points (representing Ghostbusters and ghosts) in the plane so that the lines (streams) connecting the pairs do not cross. An O(n^2 lg n)-time algorithm to solve this can be designed by utilizing a divide and conquer strategy similar to the one used in the closest pair of points problem.

1. Sort all the points by their x-coordinates.
2. Divide the set of points into two halves by drawing a vertical line through the median x-coordinate.
3. Recursively pair off Ghostbusters and ghosts in each half. Ensure that each pair consists of one Ghostbuster and one ghost from the same half.
4. Find potential cross-stream pairs by examining Ghostbusters and ghosts that are close to the dividing line. This step identifies pairs that may cause crossing streams after the recursive step.
5. For each Ghostbuster on one side of the dividing line, pair with the closest ghost on the other side such that the pair does not cause a stream cross with already established pairs. Utilize a data structure to dynamically check for intersections while pairing.
6. Repeat this for all unpaired Ghostbusters adjacent to the dividing line.
7. Merge the pairs from both halves along with the Ghostbuster-ghost pairs across the divide.

Steps 4 to 6 are critical in ensuring that no streams cross and contribute to the O(n lg n) complexity for pairing across the divide. The overall complexity is O(n^2 lg n) due to the recursive nature of the algorithm and the added complexity of checking for crossing streams.

Answer 2

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.