کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414234 680855 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exact algorithms and APX-hardness results for geometric packing and covering problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Exact algorithms and APX-hardness results for geometric packing and covering problems
چکیده انگلیسی

We study several geometric set cover and set packing problems involving configurations of points and geometric objects in Euclidean space. We show that it is APX-hard to compute a minimum cover of a set of points in the plane by a family of axis-aligned fat rectangles, even when each rectangle is an ϵ-perturbed copy of a single unit square. We extend this result to several other classes of objects including almost-circular ellipses, axis-aligned slabs, downward shadows of line segments, downward shadows of graphs of cubic functions, fat semi-infinite wedges, 3-dimensional unit balls, and axis-aligned cubes, as well as some related hitting set problems. We also prove the APX-hardness of a related family of discrete set packing problems. Our hardness results are all proven by encoding a highly structured minimum vertex cover problem which we believe may be of independent interest.In contrast, we give a polynomial-time dynamic programming algorithm for geometric set cover where the objects are pseudodisks containing the origin or are downward shadows of pairwise 2-intersecting x-monotone curves. Our algorithm extends to the weighted case where a minimum-cost cover is required. We give similar algorithms for several related hitting set and discrete packing problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 112–124
نویسندگان
, ,