Bo Gotthardt

Literature Study in Kinetic Data Structures

A project in computational geometry about kinetic data structures. Pages 4-8 and 31-37 recommended for those unfamiliar with the subject.

Kinetic tournament in Lua

An implementation of a kinetic tournament data structure in Lua, used in the above project.

Papers on kinetic data structures

1. L. J. Guibas. Kinetic data structures: A state of the art report.
2. J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data.
3. Julien Basch.Kinetic data structures, Ph.D. thesis.
4. Daniel Russel.Kinetic data structures in practise, Ph.D. thesis.
5. M. A. Abam.New Data Structures and Algorithms for Mobile Data, Ph.D. thesis.
6. J. Basch., L.J. Guibas, C.D. Silverstein, and L. ZhangA Practical Evaluation Of Kinetic Data Structures
7. J. Basch, J. Erickson, L.J. Guibas, J. Hershberger and L. Zhang.Kinetic collision detection between two simple polygons.
8. Bettina Speckmann.Kinetic Data Structures for Collision Detection, Ph.D. thesis.
9. P. Agarwal, H. Kaplan and M. Sharir. Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors
10. Giora Alexandron, Haim Kaplan and Micha Sharir. Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes
11. Mohammad Reza Razzazi and Ali Sajedi. Kinetic Convex Hull Maintenance Using Nested Convex Hulls
12. Leonidas Guibas, Menelaos I. Karavelas and Daniel Russel. A computational framework for handling motion
13. Daniel Russel, Menelaos I. Karavelas and Leonidas J. Guibas. A package for exact kinetic data structures and sweepline algorithms
14. Daniel Russel and Leonidas Guibas. An Empirical Comparison of Techniques for Updating Delaunay Triangulations
15. Daniel Russel, Pankaj Agarwal, Leonidas Guibas, An Nguyen and Li Zhang. Collision Dection for Deforming Necklaces

Other stuff

Scott Aaronson. NP-complete Problems and Physical Reality.