Theoretical Performance

Let $n$ denote the number of objects. If the average number of voxels spanned by each object is bounded, the voxel method collides $O(n)$ objects and hence imposes no asymptotic overhead on the intra-voxel subscheme.

If, further, the intra-voxel subscheme is linear time, then the voxel method is also linear time overall. If the subscheme is not linear; but the number of objects in each voxel is bounded, the subscheme runs in constant time and the voxel method is again linear time.

In the parallel implementation, after a global synchronization step each voxel forms an independent serial subproblem. Thus assuming enough voxels that good load balance is possible^4.1the time required is $O(n/p+\lg p)$. For large enough $n$, the first term dominates and the time required is $O(n/p)$.