Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Geometric Algorithms for Objects in Motion

    Thumbnail
    View/Open
    Friedler_umd_0117E_11568.pdf (1013.Kb)
    No. of downloads: 465

    Date
    2010
    Author
    Friedler, Sorelle Alaina
    Advisor
    Mount, David
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1903/10908
    Collections
    • Computer Science Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility