ALCOMFT-TR-01-132

Artur Czumaj and Christian Sohler
Soft Kinetic Data Structures
Paderborn. Work package 4. May 2001.

Abstract: We introduce the framework of soft kinetic data structures (SKDS). A soft kinetic data structure is an approximate data structure that can be used to answer queries on a set of moving points with unpredictable motion. We analyze the quality of a soft kinetic data structure by giving a competetive analysis with respect to the dynamics of the system. We illustrate our approach by presenting soft kinetic data structures for maintaining classical data structures: sorted arrays, balanced search trees, heaps, and range trees. We also describe soft kinetic data structures for maintaining the Euclidean minimum spanning tree.

Postscript file: ALCOMFT-TR-01-132.ps.gz (66 kb).