Closest Pair Algorithm

[kal_crazy]

I am doing a school project which is an airplane collision detection system. 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)?

[Moschops]

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

[kal_crazy]

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 :(

[Moschops]

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.

[kal_crazy]

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%)

[Moschops]

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?

[kal_crazy]

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?

[Moschops]

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.

[vijayan121]

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

[kal_crazy]

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

[DawnofanewEra]

@Moschops...what about the angle should it be considered as well..??