Geometric Algorithms for Objects in Motion

Simple item page
dc.contributor.advisorMount, Daviden_US
dc.contributor.authorFriedler, Sorelle Alainaen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2010-10-07T06:02:45Z
dc.date.available2010-10-07T06:02:45Z
dc.date.issued2010en_US
dc.description.abstractIn 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.en_US
dc.identifier.urihttp://hdl.handle.net/1903/10908
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledComputational Geometryen_US
dc.subject.pquncontrolledData Structuresen_US
dc.subject.pquncontrolledKinetic Dataen_US
dc.titleGeometric Algorithms for Objects in Motionen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Friedler_umd_0117E_11568.pdf
Size:
1013.42 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations