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