کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952014 1442000 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing conforming partitions of orthogonal polygons with minimum stabbing number
ترجمه فارسی عنوان
محاسبه پارتیشن های سازگار از چند ضلعی های متعامد با حداقل تعداد ریش تراش
کلمات کلیدی
چند ضلعی ارتجاعی، پارتیشن های سازگار، تعداد پایدار الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be an orthogonal polygon with n vertices. A partition of P into rectangles is called conforming if it results from cutting P along a set of interior-disjoint line segments, each having both endpoints on the boundary of P. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside P. In this paper, we consider the problem of finding a conforming partition of P with minimum stabbing number. We first give an O(nlog⁡n)-time algorithm to solve the problem when P is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP-hard if P is allowed to have holes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 689, 15 August 2017, Pages 157-168
نویسندگان
, ,