2008年9月
Performance analysis of a collision detection algorithm of spheres based on slab partitioning
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
- ,
- 巻
- E91A
- 号
- 9
- 開始ページ
- 2308
- 終了ページ
- 2313
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietfec/e91-a.9.2308
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
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.
- リンク情報
-
- DOI
- https://doi.org/10.1093/ietfec/e91-a.9.2308
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902275035445570
- CiNii Articles
- http://ci.nii.ac.jp/naid/10026851353
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000259767300006&DestApp=WOS_CPL
- ID情報
-
- DOI : 10.1093/ietfec/e91-a.9.2308
- ISSN : 0916-8508
- eISSN : 1745-1337
- J-Global ID : 200902275035445570
- CiNii Articles ID : 10026851353
- Web of Science ID : WOS:000259767300006