球体衝突の探知

最近計算的な幾何学の論文を読みました。
スタンフォード大学のGuibas教授とサムサング社の方が新しい球体衝突探知アルゴリズムを研究しました。
Spherical collision detection is of interest, because objects in games, crowd simulations, or particle simulations can be simplified as spheres. Thus, an efficient way to detect collisions among a large group of such objects, particularly in a case where their trajectories are unknown, can have many applications.
The fundamental assumption regarding the spheres is that the maximum norm of the acceleration (A) is bounded. Two constructs are introduced: time-varying bounds and subspaces. The time-varying bounds are spheres which indicate all possible areas where the sphere can be at a given time. Thus, it is represented by the position of the center of the bound, or x(t), and the radius of the bound r(t). A derivation involving Taylor's Theorem indicates that the distance between the center of the bound and the actual center of the sphere is bounded by (A/2)(t-t0)^2.
Taylor's theorem states:
f(t) = f(t0) + (f'(t0)/1!)(t-t0) + (f''(t0)/2!)(t-t0)^2 + remainder

Thus, r(t) is expressed as (A/2)(t-t0)^2 +r
where r is the original radius of the sphere.
x(t) is written as x(t0) + v(t0)(t-t0)
where v(t0) is the original velocity of the sphere.
Thus, the bound moves through space at velocity v(t0).

Subspaces are cubes which divide up the region in which the spheres move. The lengths of the sides are at least twice the diameter of the largest sphere. There are actually multiple grids of different-sized cubes, it seems, to facilitate collision detection, but I did not really understand why the grids are useful.
As the time-bound sphere moves, it traces out a parabolic horn whose cross section is the aforementioned sphere. The center and radius initially correspond to that of the actualsphere. Unlike the actual spheres, time-varying bounds have a predictable trajectory. Thus, collision checks on the spheres are made by determining whether or not their time-varying bounds collide. The reason for this is that checking all pairs of spheres is O(n^2), which can be time consuming if done for a large number spheres over several time intervals.
Each subspace contains a constant number of non-intersecting spheres, due to the assumption that the length of the sides is a constant multiple of the diameter of the largest sphere, which in turn is a constant multiple of the diameter of the smallest sphere. The subspaces are stored in a binary search tree known as a subspace tree. Each non-empty subspace is a leaf containing a list of spheres intersecting it. There are at most eight subspaces intersecting a sphere.