## 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}).

keywords: Computational Geometry, Convex Hulls, Data Imprecision

### Thesis

Maarten Lรถffler

Smallest and Largest Convex Hulls for Imprecise Points

INF/SCR-04-75, 2005

back to list