Not Yet Answered # Closest Pair Algorithm

Moschops 683 Discussion Starter kal_crazy 13 Moschops 683 Discussion Starter kal_crazy 13 Moschops 683 Discussion Starter kal_crazy 13 Moschops 683 vijayan121 1,152 Discussion Starter kal_crazy 13 Hey, so I wanna ask how I need to create a method who will remove word if in that word is 2 same chars. Example: "Potato" in this word there is a 2 "o" chars so this word will need to be removed. "Forum" in this word there is no ...

Hi I'm having a problem implementing a mini shopping cart drop down in the header to show the user all the products they have in their shopping cart. It seems the only solution for this is Ajax, and I've looked all over and can't find anything that I could possibly ...

0

What ideas do you have already? You must have at least one; tell us that, and we can go from there.

0

I know that we need to sort the points according to their x-coordinates

then divide the set into two equal sized parts

Recursively compute the minimal distance in each part

This is a new topic in our class that is why I am having a tough time completing this project :(

0

So you're given a list of points? What are the points? Are they every position the planes will ever have? What about time? Do you have the time that the plane is at each point?

Think higher level first. I read your three steps and I don't see at all how they help you work out if two planes will collide. Saying that two planes will be in the same place on two different days is no help.

0

This is the project question:

Description

You have been awarded a contract to design and implement an improved air collision detection system for Safe Airport. Your surveillance system will continuously monitor air traffic within a 100-mile radius of the airport. It will identify the closet pair of aircraft at any given time; if the closest distance is less than 500 feet, the system will sound an alarm. We assume that all aircraft fly at the same height of 10,000 feet. As part of the deliverables, you will demonstrate that your solution outperforms solutions implemented at other airports.

Implementation

You will simulate air traffic by continuously updating the position of each aircraft. You may assume that aircrafts arrive within your surveillance area with a constant arrival rate and that their course and speed remain constant. Airplanes travel at speeds between 100 and 1000 knots. Once an aircraft leaves your surveillance area, you are no longer responsible for it. You will implement three different surveillance algorithms as follows:

1. Simulate the arrival at, travel through and departure of aircraft from your area of surveillance. (35%) 2. Implement the straightforward closest pair algorithm which runs in O(n2). (15%) 3. Implement an improved closest pair algorithm which runs in O(n log2n). (30%) 4. Implement the fastest closest pair algorithm which runs in O(n log n). (20%)

0

This is simpler than at first seemed. This is not really a "will they collide" detector; it's a "closer than 500 feet" detector, which is much easier.

Start at the beginning. Have you done step one?

*Edited 3 Years Ago by Moschops*

0

Sorry for making it complicated. I guess i should have directly posted the project description :/

I am doing three projects concurrently. So I have not started with this project yet. Can you please give a brief idea on step one?

0

Pick a time step. One second, perhaps, or one minute, or whatever you like. Every plane has an x-position and a y-position. Every plane has an x-speed and a y-speed.

Make a list of every plane's location at time zero.

Then make a list of every plane's location at time one, using the x and y speed to update the x and y position.

Then make a list of every plane's location at time two.

Keep doing this until all the planes have left your 100 mile radius.

0

Can anyone show me a few examples or pseudocode of implementation of closest pair algorithm O(n^2), O(n log^2 n), O(n log n)?

The assignment states that a simple linear search (quadratic time) is all that is required:

if the closest distance is less than 500 feet, the system will sound an alarm. .. Implement the straightforward closest pair algorithm which runs in O(n^2).

If you are interested in exploring a faster O( N log N ) algorithm, this illustrates one such algorithm (using a partition tree):

http://www.drdobbs.com/a-template-for-the-nearest-neighbor-prob/184401449?pgno=1

0

Im having a tough time doing part 3 of the question. Can anyone help?

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I don’t want at this stage work on a big separate project as I've already got plenty ...