
For FullText 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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E91A
No.9
pp.23082313 Publication Date: 2008/09/01
Online ISSN: 17451337 Print ISSN: 09168508 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 ddimensional 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.

