Article ID: | iaor2010133 |
Volume: | 56 |
Issue: | 2 |
Start Page Number: | 235 |
End Page Number: | 269 |
Publication Date: | Feb 2010 |
Journal: | Algorithmica |
Authors: | Lffler Maarten, Kreveld Marc |
Keywords: | programming: linear |
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from