The expected running time of hierarchical collision detection
Jan Klein, Gabriel Zachmann · 2005
We propose a model to analyze the expected running time of hierarchical collision detection that utilizes bounding volume hierarchies (BVHs). It depends on two characteristic parameters: the overlap of the root BVs and the BV diminishing factor within the hierarchies. We show that the average running time is in O(n) or even in O(log n) for realistic cases, where n is the number of leaves. Our theoretical analysis is verified by practical experiments.