Data Structures for Mobile Data

A kinetic data structure (KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a conceptual framework for kinetic data structures, propose a number of criteria for the quality of such structures, and 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. 1 Introduction We present a set of novel data structures for the efficient maintenance of various continuous and discrete attributes of mobile data. For example, given n points moving continuously in the plane, we give methods for maintaining their convex hull or the separation of their closest pair. We call the combinatorial description of these attributes a configuration function of the mobile data 1 . Since motio...