Largest and smallest convex hulls for imprecise points

Largest and smallest convex hulls for imprecise points

0.00 Avg rating0 Votes
Article ID: iaor2010133
Volume: 56
Issue: 2
Start Page Number: 235
End Page Number: 269
Publication Date: Feb 2010
Journal: Algorithmica
Authors: ,
Keywords: programming: linear
Abstract:

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 O(n log n) to O(n13), and prove NP-hardness for some other variants.

Reviews

Required fields are marked *. Your email address will not be published.