کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5775819 1631747 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Stabbing segments with rectilinear objects
ترجمه فارسی عنوان
توقف بخش با اشیاء مستقیم
کلمات کلیدی
هندسه محاسباتی، الگوریتم ها، بخش های خط، مشکالت پایدار مشکلات طبقه بندی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
چکیده انگلیسی
Given a set S of n line segments in the plane, we say that a region R⊆R2 is a stabber for S if R contains exactly one endpoint of each segment of S. In this paper we provide optimal or near-optimal algorithms for reporting all combinatorially different stabbers for several shapes of stabbers. Specifically, we consider the case in which the stabber can be described as the intersection of axis-parallel halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3-sided rectangles, or rectangles). The running times are O(n) (for the halfplane case), O(nlog n) (for strips, quadrants, and 3-sided rectangles), and O(n2log n) (for rectangles).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 309, 15 September 2017, Pages 359-373
نویسندگان
, , , , ,