کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430912 | 688229 | 2008 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating largest convex hulls for imprecise points
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 4, December 2008, Pages 583–594
Journal: Journal of Discrete Algorithms - Volume 6, Issue 4, December 2008, Pages 583–594
نویسندگان
Marc van Kreveld, Maarten Löffler,