Geometric Algorithms for Objects in Motion

Abstract

In this thesis, the theoretical analysis of real-world motivated problems regarding objects in motion is considered. Specifically, four major results are presented addressing the issues of robustness, data collection and compression, realistic theoretical analyses of this compression, and data retrieval.

Robust statistics is the study of statistical estimators that are robust to data outliers. The combination of robust statistics and data structures for moving objects has not previously been studied. In studying this intersection, we consider a problem in the context of an established kinetic data structures framework (called KDS) that relies on advance point motion information and calculates properties continuously. Using the KDS model, we present an approximation algorithm for the kinetic robust k-center problem, a clustering problem that requires k clusters but allows some outlying points to remain unclustered.

For many practical problems that inspired the exploration into robustness, the KDS model is inapplicable due to the point motion restrictions and the advance flight plans required. We present a new framework for kinetic data that allows calculations on moving points via sensor-recorded observations. This new framework is one of the first within the computational geometry community to allow analysis of moving points without a priori knowledge of point motion. Analysis within this framework is based on the entropy of the point set's motion, so efficiency bounds are a function of observed complexity instead of worst-case motion. Analysis is also considered under the more realistic assumptions of empirical entropy and assumptions of limited statistical independence. A compression algorithm within this framework is presented in order to address the storage issues created by the massive data sets sensors collect. Additionally, we show experimentally that this framework and accompanying compression scheme work well in practice. In order to allow for retrieval of the collected and compressed data, we present a spatio-temporal range searching structure that operates without the need to decompress the data. In sum, the collection scheme, compression algorithm, theoretical analyses, and retrieval data structures provide a practical, yet theoretically sound, framework within which observations and analyses can be made of objects in motion.