Geometric Computations on Indecisive Points

We study computing with indecisive point sets. Such points have spatial uncertainty where the true location is one of a finite number of possible locations. This data arises from probing distributions a few times or when the location is one of a few locations from a known database. In particular, we study computing distributions of geometric functions such as the radius of the smallest enclosing ball and the diameter. Surprisingly, we can compute the distribution of the radius of the smallest enclosing ball exactly in polynomial time, but computing the same distribution for the diameter is #P-hard. We generalize our polynomial-time algorithm to all LP-type problems. We also utilize our indecisive framework to deterministically and approximately compute on a more general class of uncertain data where the location of each point is given by a probability distribution.

keywords: Computational Geometry, Data Imprecision

Conference Proceedings (peer-reviewed)

Allan Jørgensen, Jeff Phillips, Maarten Löffler
Geometric Computations on Indecisive Points
Proc. 12th Algorithms and Data Structures Symposium
LNCS 6844, 536–547, 2011
http://dx.doi.org/10.1007/978-3-642-22300-6_45

Archived Publication (not reviewed)

Allan Jørgensen, Jeff Phillips, Maarten Löffler
Geometric Computations on Indecisive Points
1205.0273, 2012
http://arXiv.org/abs/1205.0273

back to list