slides
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.