Collision detection (part 2)

January 19, 2015 in Programming by Adrian Marius

Last time, we discussed collision detection in general and surveyed some techniques for narrow phase collision detection.  In this article we will go into more detail on broad phase collision detection for closed axis-aligned boxes.  In the late 1970’s and early 1980’s, this problem attracted an enormous amount of attention due to its applications in VLSI design, resulting in many efficient algorithms and data structures.  Here we survey some of the general approaches to this problem and review some analytical results.