Geometric Measures on Imprecise Points in Higher Dimensions

Hein Kruger, Maarten Löffler

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    Abstract

    Imprecision in input data is an important obstacle to the application of techiniques from computational geometry in practical situations. Recently, a growing amount of research acknowledges this issue. However, the focus has mostly been on the planar case, while many applications work on data in three or more dimensions. In particular, we study the problem of computing lower and upper bounds on the possible values of several basic geometric measures on point sets in higher dimensions. We present results for two extent measures on point sets: the axis-aligned minimum bounding box and the width. The results range from algorithms that run in linear time in any dimensions, to running times of n^O(d) and NP-hardness proofs. Some problems are left for future work.
    Original languageEnglish
    Title of host publicationProc. 25th European Workshop on Computational Geometry
    Pages121-124
    Number of pages4
    Publication statusPublished - 2009

    Keywords

    • CG, IMP, HD

    Fingerprint

    Dive into the research topics of 'Geometric Measures on Imprecise Points in Higher Dimensions'. Together they form a unique fingerprint.

    Cite this