## 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

### Archived Publication (not reviewed)

Allan Jørgensen, Jeff Phillips, Maarten Löffler

Geometric Computations on Indecisive Points

1205.0273, 2012

back to list