Geometric Measures on Imprecise Points in Higher Dimensions

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 nO(d) and NP-hardness proofs. Some problems are left for future work.

keywords: Computational Geometry, Higher Dimensions, Data Imprecision

Workshop or Poster (weakly reviewed)

Hein Kruger, Maarten Löffler
Geometric Measures on Imprecise Points in Higher Dimensions
Proc. 25th European Workshop on Computational Geometry
121–124, 2009

back to list