Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning

Takashi IMAMICHI  Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.9   pp.2308-2313
Publication Date: 2008/09/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
collision detection,  slab partitioning,  plane sweep method,  polynomial algorithm,  computational geometry,  

Full Text: PDF(178.2KB)
>>Buy this Article


Summary: 
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded, then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.