  We study computing geometric problems on uncertain points. An uncertain point
is a point that does not have a fixed location, but rather is described by a
probability distribution. When these probability distributions are restricted
to a finite number of locations, the points are called indecisive points. In
particular, we focus on geometric shape-fitting problems and on building
compact distributions to describe how the solutions to these problems vary with
respect to the uncertainty in the points. Our main results are: (1) a simple
and efficient randomized approximation algorithm for calculating the
distribution of any statistic on uncertain data sets; (2) a polynomial,
deterministic and exact algorithm for computing the distribution of answers for
any LP-type problem on an indecisive point set; and (3) the development of
shape inclusion probability (SIP) functions which captures the ambient
distribution of shapes fit to uncertain or indecisive point sets and are
admissible to the two algorithmic constructions.
