Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
スポンサーリンク
概要
- 論文の詳細を見る
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(nlogn+K) time with O(n+K) space, where K denotes the number of pairs of colliding spheres.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
IMAMICHI Takashi
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
-
Imamichi Takashi
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
- Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications