Kinetic Collision Detection for Convex Fat Objects
Tóm tắt
We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:
Tài liệu tham khảo
Agarwal, P.K., Basch, J., Guibas, L.J., Hershberger, J., Zhang, L.: Deformable free space tilings for kinetic collision detection. Int. J. Robot. Res. 21, 179–197 (2002)
Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognit. 17(2), 251–257 (1984)
Basch, J., Guibas, L., Zhang, L.: Proximity problems on moving points. In: Proc. 13th Symposium on Computational Geometry, pp. 344–351 (1997)
Basch, J., Guibas, L., Hershberger, J.: Data structures for mobile data. J. Algorithms 31, 1–28 (1999)
Basch, J., Erickson, J., Guibas, L.J., Hershberger, J., Zhang, L.: Kinetic collision detection for two simple polygons. Comput. Geom.: Theory Appl. 27(3), 211–235 (2004)
de Berg, M.: Linear size binary space partitions for uncluttered scenes. Algorithmica 28, 353–366 (2000)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000)
de Berg, M., Comba, J., Guibas, L.: A segment-tree based kinetic BSP. In: Proc. 17th Symposium on Computational Geometry, pp. 134–140 (2001)
de Berg, M., Katz, M., van der Stappen, F., Vleugels, J.: Realistic input models for geometric algorithms. Algorithmica 34, 81–97 (2002)
de Berg, M., David, H., Katz, M., Overmars, M., van der Stappen, F., Vleugels, J.: Guarding scenes against invasive hypercubes. Comput. Geom.: Theory Appl. 26, 99–117 (2003)
Coming, D., Staadt, O.: Kinetic sweep and prune for collision detection. In: Proc. Workshop on Virtual Reality Interactions and Physical Simulations, pp. 81–90 (2005)
Erickson, J., Guibas, L., Stolfi, J., Zhang, L.: Separation-sensitive collision detection for convex objects. In: Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 327–336 (1999)
Guibas, L.: Kinetic data structures: a state of the art report. In: Proc. 3rd Workshop on Algorithmic Foundations of Robotics, pp. 191–209 (1998)
Guibas, L.: Modeling motion. In: Goodman, J., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1117–1134. CRC Press (2004)
Guibas, L., Xie, F., Zhang, L.: Kinetic collision detection: algorithms and experiments. In: Proc. International Conference on Robotics and Automation, pp. 2903–2910 (2001)
Katz, M.: 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects. Comput. Geom.: Theory Appl. 8, 299–316 (1998)
Kim, D., Guibas, L., Shin, S.Y.: Fast collision detection among multiple moving spheres. IEEE Trans. Vis. Comput. Graph. 4(3), 230–242 (1998)
Kim, H.K., Guibas, L., Shin, S.Y.: Efficient collision detection among moving spheres with unknown trajectories. Algorithmica 43, 195–210 (2005)
Kirkpatrick, D., Speckmann, B.: Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. In: Proc. 18th ACM Symposium on Computational Geometry, pp. 179–188 (2002)
Kirkpatrick, D., Snoeyink, J., Speckmann, B.: Kinetic collision detection for simple polygons. Int. J. Comput. Geom. Appl. 12(1&2), 3–27 (2002)
Lin, M., Manocha, D.: Collision and proximity queries. In: Goodman, J., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 787–807. CRC Press (2004)
van der Stappen, A.F.: Motion planning amidst fat obstacles. Ph.D. thesis, Utrecht University, Utrecht, the Netherlands (1994)
Zhou, Y., Suri, S.: Analysis of a bounding box heuristic for object intersection. J. ACM 46(6), 833–857 (1999)