Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235466] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, P; Guibas, L; Nguyen, A; Russel, D; Zhang, L, Collision detection for deforming necklaces, Computational Geometry, vol. 28 no. 2-3 SPEC. ISS. (2004), pp. 137-163, ISSN 0925-7721 [doi]
    (last updated on 2018/10/16)

    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 macro-molecules, 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 self-collision 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(nlogn) in two dimensions and O(n 2-2/d) in d-dimensions, d3. 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 self-collisions of a necklace in a way that is complementary to the sphere hierarchy. © 2004 Elsevier B.V.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320