
P. Agarwal, L. Guibas, A. Nguyen, D. Russel, and L. Zhang, Collision Detection for Deforming Necklaces, Computational Geometry: Theory and Applications, pp. 137163, 2004
Abstract:
In this paper, we propose to study deformable necklaces  flexible
chains of balls, called beads, in which only adjacent balls may
intersect. Such objects can be used to model macromolecules,
muscles, ropes, and other linear objects in the physical world. We
exploit this linearity to develop geometric structures associated
with necklaces that are useful for collision detection in physical
simulations. We show how these structures can be implemented
efficiently and maintained under necklace deformation. In particular,
we study a bounding volume hierarchy based on spheres which can be
used for collision and selfcollision detection of deforming and
moving necklaces. As our theoretical and experimental results show,
such a hierarchy is easy to compute and, more importantly, is also
easy to maintain when the necklace deforms. Using this hierarchy, we
achieve a collision detection upper bound of $O(n\log n)$ in two
dimensions and $O(n^{22/d})$ in $d$dimensions, $d\geq 3$. To our
knowledge, this is the first subquadratic bound proved for a
collision detection algorithm using predefined hierarchies. In
addition, we show that the power diagram, with the help of some
additional mechanisms, can be used to detect selfcollisions of a
necklace in a way that is complementary to the sphere hierarchy.
Bibtex:
@article{agnrzcddn04,
, author = "Pankaj Agarwal and Leonidas Guibas and An Nguyen and
Daniel Russel and Li Zhang
, journal = "Computational Geometry: Theory and Applications"
, title = "Collision detection for deforming necklaces"
, year = 2004
, volume = 28
, pages = "137163"
}

