Math @ Duke

Publications [#235448] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Basch, J; Guibas, LJ; Hershberger, J; Zhang, L, Deformable freespace tilings for kinetic collision detection,
International Journal of Robotics Research, vol. 21 no. 3
(2002),
pp. 179197 [doi]
(last updated on 2018/05/27)
Abstract: We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume hierarchies, our method is based on deformable tilings of the free space surrounding the polygons. The basic shape of our tiles is that of a pseudotriangle, a shape sufficiently flexible to allow extensive deformation, yet structured enough to make detection of selfcollisions easy. We show different schemes for maintaining pseudotriangulations as a kinetic data structure, and we analyze their performance. Specifically, we first describe an algorithm for maintaining a pseudotriangulation of a point set, and show that the pseudotriangulation changes only quadratically many times if points move along algebraic arcs of constant degree. In addition, by refining the pseudotriangulation, we show triangulations of points that only change about O (n7/3) times for linear motion. We then describe an algorithm for maintaining a pseudotriangulation of a set of convex polygons. Finally, we extend our algorithm to the general case of maintaining a pseudotriangulation of a set of moving or deforming simple polygons.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

