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

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
نویسندگان
, ,