Datastructure and algorithm to detect collisions of irregular shaped moving objects

Question

I came across this interview question

Many irregularly shaped objects are moving in random directions. Provide a data structure and algorithm to detect collisions. Remember that the number of objects is in the millions.

I am assuming that every object would have an x and y coordinate. Other assumptions are most welcome. Also a certain kind of tree should be used, I suppose, but I am clueless about the algorithm.

Any suggestions?

Answer 1

I would have a look at the Plane Sweep Algorithm or the Bently-Ottmann Algorithm. It uses plane sweep to determine in O(n log(n)) time (and O(n) space) the intersection of lines on a euclidian plane.

Answer 2

Most likely what you want is to sub-divide the plane with a space-filling-curve like a z-curve or a hilbert-curve and thus reducing the complexity of a 2D problem to a 1D problem. Look for quadtree.

Link: http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html