Smallest and Largest Convex Hulls for Imprecise Points

It is useful to be able to compute the convex hull of a set of imprecise points, points that have no fixed location but are allowed to move within a given region. The convex hull of such a set is not unique, so lower and upper bounds on some measure, such as area or perimeter, are needed. We give polynomial time algorithms for many variants of this problem, ranging in running time from $O(n log n)$ to $O(n^10)$.