کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419088 681741 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Covering points with orthogonal polygons
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Covering points with orthogonal polygons
چکیده انگلیسی

We address the problem of covering points with orthogonal polygons. Specifically, given a set of nn points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex   polygon, if any, can be done in O(nlogn)O(nlogn) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 92–99
نویسندگان
, , ,