A Review on Kinetic Data Structures
DOI. 10.54798/ENXW6126
Keywords:
data, structure, kinetic, delaunay, triangulationAbstract
Kinetic Data Structures are a special way to model continuous collision detection due to the model and combination of the state of geometrical and motion configuration [Gui98], [GKR04], [Gui04] and [Got08]. Kinetication is a process focused on transforming an algorithm working on static data into a data structure valid for continuously changing data. A Kinetic Data Structure is a structure using some attributes in the input set, it includes a set of proofs that guarantee the attributes stay valid, and has a system that updates the data structure when the proofs or the structure of the attributes are no longer valid. The most widely utilized Kinetic Data Structures are: Collision Detection, Delaunay Triangulation, Convex Hull, Sorted List, Spanner, Voronoi, amongst others.
References
[AAdY06] Mohammad Ali Abam, Pankaj K. Agarwal, Mark de Berg, and Hai Yu. Out-of-order event processing in kinetic data structures. In ESA'06, pages 624-635, 2006.
[Aba07] Mohammad Ali Abam. New Data Structures and Algorithms for Mobile Data. PhD thesis, Technische Universiteit Eindhoven, 2007.
[ABd+00] Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, and John Hershberger. Lower bounds for kinetic planar subdivisions. Discrete & Computational Geometry, pages 721-733, 2000.
[ABT07] Umut A. Acar, Guy E. Blelloch, and Kanat Tangwongsan. Kinetic 3d convex hulls via self-adjusting computation. In Jeff Erickson, editor, Symposium on Computational Geometry, pages 129-130. ACM, 2007.
[ABTT08] Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Duru Türkoglu. Robust kinetic convex hulls in 3d. In Proceedings of the 16th annual European symposium on Algorithms, ESA '08, pages 29-40, Berlin, Heidelberg, 2008. Springer-Verlag.
[Ad05] Mohammad Ali Abam and Mark de Berg. Kinetic sorting and kinetic convex hulls. In Joseph S. B. Mitchell and Gunter Rote, editors, Symposium on Computational Geometry, pages 190-197. ACM, 2005.
[Ad09] Mohammad Ali Abam and Mark de Berg. Kinetic spanners in rd. In John Hershberger and Efi Fogel, editors, Symposium on Computational Geometry, pages 43-50. ACM, 2009.
[AdG08] Mohammad Ali Abam, Mark de Berg, and Joachim Gudmundsson. A simple and efficient kinetic spanner. In Monique Teillaud, editor, Symposium on Computational Geometry, pages 306-310. ACM, 2008.
[AdhPS06a] Mohammad Ali Abam, Mark de Berg, Sheung hung Poon, and Bettina Speckmann. Kinetic collision detection for balls rolling on a plane, 2006.
[AdhPS06b] Mohammad Ali Abam, Mark de Berg, Sheung hung Poon, and Bettina Speckmann. Kinetic collision detection for convex fat objects. In Proceedings of the 14th conference on Annual European Symposium - Volume 14, pages 4-15, London, UK, 2006. Springer-Verlag.
[AEG98] Pankaj K. Agarwal, Jeff Erickson, and Leonidas J. Guibas. Kinetic binary space partitions for intersecting segments and disjoint triangles. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, SODA '98, pages 107-116, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics.
[AEGH98] Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, and Monika R. Henzinger. Parametric and kinetic minimum spanning trees. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS '98, pages 596-, Washington, DC, USA, 1998. IEEE Computer Society.
[AGG+10] Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, and Micha Sharir. Kinetic stable delaunay graphs. In Proceedings of the 2010 annual symposium on Computational geometry, SoCG '10, pages 127-136, New York, NY, USA, 2010. ACM.
[AHT11] Umut A. Acar, Benoît Hudson, and Duru Türkoglu. Kinetic mesh refinement in 2d. In Proceedings of the 27th annual ACM symposium on Computational geometry, SoCG '11, pages 341-350, New York, NY, USA, 2011. ACM.
[AKS08] Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algorithms, 5:4:1-4:37, December 2008.
[Bas99] Julien Basch. Kinetic Data Structures. PhD thesis, Stanford University, Stanford, CA, USA, 1999.
[BEG+04] Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, and Li Zhang. Kinetic collision detection between two simple polygons. Comput. Geom. Theory Appl., 27:211-235, March 2004.
[BGH97] Julien Basch, Leonidas J. Guibas, and John Hershberger. Data structures for mobile data. In SODA, pages 747-756, 1997.
[BGSZ97] Julien Basch, Leonidas J. Guibas, Craig D. Silverstein, and Li Zhang. A practical evaluation of kinetic data structures. In Proceedings of the thirteenth annual symposium on Computational geometry, SCG '97, pages 388-390, New York, NY, USA, 1997. ACM.
[BSDMH05] Tilo Beyer, Gernot Schaller, Andreas Deutsch, and Michael Meyer-Hermann. Parallel dynamic and kinetic regular triangulation in three dimensions. Computer Physics Communications, 172(2):86-108, November 2005.
[CDZ11] Yam Ki Cheung, Ovidiu Daescu, and Marko Zivanic. Kinetic red-blue minimum separating circle. In Proceedings of the 5th international conference on Combinatorial optimization and applications, COCOA'11, pages 448-463, Berlin, Heidelberg, 2011. Springer-Verlag.
[CS01] Artur Czumaj and Christian Sohler. Soft kinetic data structures. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, SODA '01, pages 865-872, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.
[CS05] Daniel S. Coming and Oliver G. Staadt. Kinetic sweep and prune for collision detection. In In Proc. Workshop on Virtual Reality Interactions and Physical Simulations, pages 81-90, 2005.
[CS06] Daniel S. Coming and Oliver G. Staadt. Kinetic sweep and prune for multi-body continuous motion. Computers & Graphics, 30:439-449, 2006.
[DEGS10] Erik D. Demaine, Sarah Eisenstat, Leonidas J. Guibas, and André Schulz. Kinetic minimum spanning circle. In In Proceedings of the Fall Workshop on Computational Geometry, New York, USA, 2010.
[DM08] Olivier Devillers and Pedro Machado Manh~aes de Castro. State of the art:Updating delaunay triangulations for moving points. Rapport de recherché RR-6665, INRIA, 2008.
[dRS11] Mark de Berg, Marcel Roeloffzen, and Bettina Speckmann. Kinetic convex hulls and delaunay triangulations in the black-box model. In Symposium on Computational Geometry, pages 244-253, 2011.
[FM10] Sorelle A. Friedler and David M. Mount. Approximation algorithm for the kinetic robust k-center problem. Comput. Geom. Theory Appl., 43:572- 586, August 2010.
[GD06] Christopher M. Gold and Maciej Dakowicz. Kinetic voronoi/Delaunay drawing tools. In Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering, ISVD '06, pages 76-84, Washington, DC, USA, 2006. IEEE Computer Society.
[GKR04] Leonidas J. Guibas, Menelaos Ioannis Karavelas, and Daniel Russel. A computational framework for handling motion. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, pages 129-141, 2004.
[Got08] Bo Gotthardt. Literature study in kinetic data structures, 2008.
[Gui98] Leonidas J. Guibas. Kinetic data structures: a state of the art report. In Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, WAFR '98, pages 191-209, Natick, MA, USA, 1998. A. K. Peters, Ltd.
[Gui01] Leonidas J. Guibas. Kinetic data structures, 2001.
[Gui04] Leonidas J. Guibas. Kinetic data structures. In Handbook of Data Structures and Applications. CRC Press, 2004.
[GXZ01] Leonidas J. Guibas, Feng Xie, and Li Zhang. Kinetic collision detection: Algorithms and experiments. In ICRA'01, pages 2903-2910, 2001.
[HBF07] Jérome Härri, Christian Bonnet, and Fethi Filali. Kinetic graphs: a framework for capturing the dynamics of mobile structures in manet. In Proceedings of the 2nd ACM workshop on Performance monitoring and measurement of heterogeneous wireless and wired networks, PM2HW2N '07, pages 88-91, New York, NY, USA, 2007. ACM.
[Her04] John Hershberger. Kinetic collision detection with fast flight plan changes. Inf. Process. Lett., 92:287-291, December 2004.
[KRS10] Haim Kaplan, Natan Rubin, and Micha Sharir. A kinetic triangulation scheme for moving points in the plane. In Jack Snoeyink, Mark de Berg, Joseph S. B. Mitchell, Gunter Rote, and Monique Teillaud, editors, Symposium on Computational Geometry, pages 137-146. ACM, 2010.
[KS01] David Kirkpatrick and Bettina Speckmann. Separation sensitive kinetic separation structures for convex polygons. In Revised Papers from the Japanese Conference on Discrete and Computational Geometry, JCDCG '00, pages 222-236, London, UK, 2001. Springer-Verlag.
[KSS00] David Kirkpatrick, Jack Snoeyink, and Bettina Speckmann. Kinetic collision detection for simple polygons. In Proceedings of the sixteenth annual symposium on Computational geometry, SCG '00, pages 322-330, New York, NY, USA, 2000. ACM.
[MD08] Pedro Machado Manh~aes de Castro and Olivier Devillers. Delaunay triangulations for moving points. Research Report RR-6750, INRIA, 2008.
[MTAD09] Pedro Machado Manh~aes de Castro, Jane Tournois, Pierre Alliez, and Olivier Devillers. Filtering relocations on a delaunay triangulation. In Proceedings of the Symposium on Geometry Processing, SGP '09, pages 1465-1474, Aire-la-Ville, Switzerland, Switzerland, 2009. Eurographics Association.
[RKG07] Daniel Russel, Menelaos Ioannis Karavelas, and Leonidas J. Guibas. A package for exact kinetic data structures and sweepline algorithms. Comput. Geom. Theory Appl., 38:111-127, September 2007.
[Rus07] Daniel Russel. Kinetic data structures in practice. PhD thesis, Stanford University, Stanford, CA, USA, 2007.
[Spe01] Bettina Speckmann. Kinetic Data Structures for Collision Detection. PhD thesis, Müunster Germany, 2001.
[SSV07] Jagan Sankaranarayanan, Hanan Samet, and Amitabh Varshney. A fast all nearest neighbor algorithm for applications involving large point-clouds. Comput. Graph., 31:157-174, April 2007.
[VK08] Tomás Vomácka and Ivana Kolingerová. Computation of topologic events in kinetic delaunay triangulation using sturm sequences of polynomials. In SIGRAD 2008, pages 57-64, Linkoping, 2008. University Electronic Press.
[Vom08a] Tomás Vomácka. Delaunay triangulation of moving points. In CESCG 2008, pages 67-74, Vienna, 2008. Vienna University of Technology.
[Vom08b] Tomás Vomácka. Delaunay Triangulation of Moving Points in the Plane. PhD thesis, University of West Bohemia, Pilsen, Czech Republic, 2008.
[WZ06] René Weller and Gabriel Zachmann. Kinetic separation lists for continuous collision detection of deformable objects. In VRIPHYS'06, pages 33-42, 2006.
[YCLL05] Taewon Yoo, Sunghee Choi, Hyonik Lee, and Jinwon Lee. Distributed kinetic delaunay triangulation, 2005.
[ZSW+10] Yuanfeng Zhou, Feng Sun, Wenping Wang, Jiaye Wang, and Caiming Zhang. Fast updating of delaunay triangulation of moving points by bi-cell filtering. Computer Graphics Forum, 29(7):2233-2242, 2010.
[ZW06] Gabriel Zachmann and Rene Weller. Kinetic bounding volume hierarchies for deformable objects. In Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, VRCIA '06, pages 189-196, New York, NY, USA, 2006. ACM.
[ZY00] Dongliang Zhang and Matthew M. F. Yuen. Collision detection for clothed human animation. In Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, PG '00, pages 328-, Washington, DC, USA, 2000. IEEE Computer Society.
Published
License
Copyright (c) 2022 Revista Cientifica Emprendimiento Científico Tecnologico
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
