کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652743 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Covering oriented points in the plane with orthogonal polygons is NP-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We address the problem of covering points with orthogonal polygons. Specifically, given a set of n grid-points in the plane each designated in advance with either a horizontal or vertical reading, we investigate the existence of an orthogonal polygon covering these n points in such a way that each edge of the polygon covers exactly one point and each point is covered by exactly one edge with the additional requirement that the reading associated with each point dictates whether the edge covering it is to be horizontal or vertical. We show that this problem is NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 303-310
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 303-310