The Possible Hull of Imprecise Points
Jeff Sember, William Evans · Canadian Conference on Computational Geometry · 2011
We pose the problem of constructing the possible hull of a set of n imprecise points: the union of convex hulls of all sets of n points, where each point is constrained to lie within a particular region of the plane. We give an optimal algorithm for the case when n = 2, and the regions are a point and a simple (possibly nonconvex) polygon. We then describe how the algorithm leads to an optimal algorithm for the case when n 2, and each region is a simple polygon. 1