Explain how to determine line in o-n lg n time

Assignment Help Data Structure & Algorithms

Reference no: EM1372103

A group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed with 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 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.

Reference no: EM1372103

Questions Cloud

Find profit-maximizing output and price : A company under monopolistic competition faces the demand curve: P = 500 - 12.5Q. The company's marginal cost is MC = 200 + 5Q.

Erikson stages of development : Explain Erikson's stages of development as each applies to your own personality formation. How did success at one stage make you for meeting the next challenge.

Concept of bureaucracy : Making direct reference to your reading assignments, discuss what is meant by the machine metaphor of modern organizations. How does this machine metaphor of organizations apply to Weber's concept of bureaucracy?

Determine average streaming media data rate : Assume we can accurately forecast set of WAPs that the taxi will visit. Determine average streaming media data rate that we can sustain by downloading prefetched data from WAPs?

Explain how to determine line in o-n lg n time : Explain how to determine such a line in O(n lg n) time. Provide the O(n^2 lg n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.

Theory of human relations : Consider the following scenario: You're a plant foreperson at a highly-productive and competitive factory. Your manager approaches you with a concern about last month's productivity for the unit for which you are responsible.

Explain about supply chain strategies : Cite industry examples for at least two of the six Supply Chain strategies introduced in class and a brief description is expected for each example.

Write program which translates letter grade into grade : Write a C++ program which translates the letter grade into a number grade. Letter grades are A B C D F, possibly followed by + or -. Their numeric values are 4, 3, 2, 1, and 0.

Develop a bipolar transistor amplifier with a voltage gain : The aim of this experiment is to develop a bipolar transistor amplifier with a voltage gain of minus 25. The amplifier must accept input signals from a source impedance of 1 kW and provide an undistorted output amplitude of 5 V when driving a 560..

User Account

All Pages