Ghostbusters and Ghosts A group of n Ghostbusters is battling n ghosts. Each Gho

Question

Ghostbusters and Ghosts

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.

a. Argue that there exists a line passing through one Ghostbuster and one ghost such that the number of Ghostbusters on one side of the line equals the number of ghosts on the same side. Describe how to find such a line in O(n lg n) time.

b. Give an O(n 2 lg n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.

Explanation / Answer

SOLUTION:-

(a):- First of all we will find the surface, a point farthest to the left which is described in the Graham scan method then rest points will be selected via angle through that point. We suppose that the surface, a point farthest to the left will be a Ghostbuster. Now we will inspect the selected points via growing angle, in order to sustaining watch of the disparity among number of inspected Ghostbusters and Ghosts. We will halt when the disparity is -1, and attach the point to the surface, a point farthest to the left. Run time will be excelled by the selection, which will accept O(n log n) time.

(b):- We will implement the algorithm mentioned above for matching the one pair of Ghostbuster and Ghost. The number of Ghostbusters and Ghosts are equal on every direction of the line made via pairing so we will implement the algorithm recursively on every direction of the line in order to detect the pairing. After doing every iteration, one direction of the line consist of no Ghostbusters or Ghosts, this is the worst case. certainly, we require n/2 overall iterations in order to detect pairing, That will result in O(n2 log n) time algorithm.

======================================================================================

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.