Data Structures for Mobile Data
Julien Basch, Leonidas J. Guibas, John E. Hershberger · Journal of Algorithms · 1999
Akinetic data structure(KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a concentual framework for kinetic data structures, we propose a number of criteria for the quality of such structures, and we describe a number of fundamental techniques for their design. We illustrate these general concepts by presenting kinetic data structures for maintaining the convex hull and the closest pair of moving points in the plane; these structures behave well according to the proposed quality criteria for KDSs.
Cited by 370 works. doi:10.1006/jagm.1998.0988
Authors
References
- Introduction to Algorithms
- Computational Geometry--An Introduction.
- Algorithms for Reporting and Counting Geometric Intersections
- Maintenance of configurations in the plane
- Davenport-Schinzel Sequences and their Geometric Applications
- Some dynamic computational geometry problems
- Constructing Belts in Two-Dimensional Arrangements with Applications
- Applications of Parametric Searching in Geometric Optimization
- Finding the upper envelope of n line segments in O(n log n) time
- Comments on “algorithms for reporting and counting geometric intersections”