For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
Takashi IMAMICHI Hiroshi NAGAMOCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
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)
collision detection, slab partitioning, plane sweep method, polynomial algorithm, computational geometry,
Full Text: PDF(178.2KB)>>
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.