Back
to indexJulien Basch and Leonidas Guibas and John Hershberger
Summary
Under the framework of the closest pair and convex hull problems, the authors describe a model that will work under mobile conditions, while the majority of the current research is with static objects. This data is maintained within a set of configuration functions that model kinetic data structures. The majority of the paper is devoted to mathematical proofs of the various structures and their kinetiezation, a process described below.
Methods
The process is called kinetization of transforming an algorithm on static data into a data structure that is valid for continuously moving data. One assumption is made: each object has a previously posted flight plan, or some kind of information about its current trajectory available. Flight plans may be updated dynamically. Each data structure has a "narrow interface" to the motion, meaning each event in the event queue corresponds to combinatorial combinations of all the events in the queue. One solution involves a heap structure to maintain all moving points, and as the points move, links are inserted between points, generating an event on the event queue. Parents may cause their child nodes to adjust accordingly simultaneously.
Keywords
kinetization, closest pair, convex hull
Rating
7
Bibtex Entry
@article{ basch96data,
author = "Julien Basch and Leonidas Guibas and John Hershberger",
title = "Data Structures for Mobile Data",
journal = "",
volume = "",
number = "",
pages = "",
year = "1996",
url = ""
}