  We study the problem of polygonal curve simplification under uncertainty,
where instead of a sequence of exact points, each uncertain point is
represented by a region, which contains the (unknown) true location of the
vertex. The regions we consider are disks, line segments, convex polygons, and
discrete sets of points. We are interested in finding the shortest subsequence
of uncertain points such that no matter what the true location of each
uncertain point is, the resulting polygonal curve is a valid simplification of
the original polygonal curve under the Hausdorff or the Fr\'echet distance. For
both these distance measures, we present polynomial-time algorithms for this
problem.
