Suppose I have N different airplanes traveling on a two dimensional rectangular plane of size 400km x 400km (i.e. it is as if all planes travel at the same altitude). Assume each airplane has a randomly generated starting and ending points. Also, assume that the airplanes can have different speeds. We assume that two airplanes will "collide" if they come within 10 km of each other. Based upon this information, how can I efficiently determine which pairs of airplanes will inevitably collide?
Update: As far as I can tell, it would require something similar to a line segment intersection algorithm, but instead of a line having zero width, it has a thickness of 20km. I'm just not sure how to incorporate the time dynamics into the detection algorithm. I suppose I could use a polygon-intersection at each (small) time step to determine if they collide, but I wanted to see if there is a more efficient way to detect it without going through pair-wise polygon intersection at each time step.