Spatial subdivision

Spatial subdivision divides objects based on their location, rather than a prearranged hierarchy. The classic spatial subdivision method is recursive coordinate bisection, or RCB. In this method, the domain is repeatedly halved by choosing an axis-aligned cutting plane and dividing the objects on one side from those on the other side- see Figure . Eventually, the subproblems are small enough that the all-pairs method is appropriate.

Figure: Recursive coordinate bisection on a set of small spheres. From left to right: problem is bisected once horizontally; recursively bisected vertically; then recursively bisected horizontally again

With axis-aligned cutting planes, we can determine which side an object belongs simply by examining its axis-aligned bounding box, so dividing the problem takes $O(n)$ time. Ignoring objects that straddle the cutting plane (and thus must be kept on both sides), and assuming each division cuts the problem into two nearly equal-sized halves, the RCB method requires $O(\lg n)$ divisions and hence runs in $O(n\lg n)$ time.

Plimpton, Attaway, Hendrickson et al. [#!Hend96!#] use a parallel RCB scheme to perform collision detection in a transient dynamics application. The parallel implementation of RCB requires at least $O(\lg p)$ synchronized communication steps, however, so the approach has a rather high synchronization overhead^1.4.

Allowing the cutting planes to have arbitrary orientation results in a binary space partition, first described by Fuchs et al. in [#!FKN80!#]. The theoretical runtime is the same as that of RCB.

Another spatial subdivision scheme is the sweep-line method, often used for line segment intersection in 2D. This method first sorts the significant points of each object by $x$ coordinates, then maintains a sorted $y$ neighbor list as it proceeds along $x$, testing each new object against its neighbors. The sorting and neighbor lists make this algorithm $O(n\lg n)$ average case, like RCB.

Several other spatial subdivision schemes have been described, such as octrees [#!Bandi95!#] and methods derived from ray tracing. By reduction to sorting, however, any subdivision scheme based on comparing object locations will require at least $O(n\lg n)$ time; with parallel implementations that require multiple synchronization steps. The voxel method, described next, in some situations achieves $O(n)$ performance with excellent parallel efficiency.