Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2308-2313
- Publication Date
- 2008/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.9.2308
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takashi IMAMICHI, Hiroshi NAGAMOCHI, "Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2308-2313, September 2008, doi: 10.1093/ietfec/e91-a.9.2308.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2308/_p
Copy
@ARTICLE{e91-a_9_2308,
author={Takashi IMAMICHI, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning},
year={2008},
volume={E91-A},
number={9},
pages={2308-2313},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2308},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2308
EP - 2313
AU - Takashi IMAMICHI
AU - Hiroshi NAGAMOCHI
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2308
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - 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.
ER -
English
