Largest and Smallest Convex Hulls for Imprecise Points |
| |
Authors: | Maarten Löffler Marc van Kreveld |
| |
Affiliation: | 1. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
|
| |
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(nlog n) to O(n
13), and prove NP-hardness for some other variants. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|