کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5775819 | 1631747 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stabbing segments with rectilinear objects
ترجمه فارسی عنوان
توقف بخش با اشیاء مستقیم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هندسه محاسباتی، الگوریتم ها، بخش های خط، مشکالت پایدار مشکلات طبقه بندی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
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
Journal: Applied Mathematics and Computation - Volume 309, 15 September 2017, Pages 359-373
نویسندگان
Mercè Claverol, Delia Garijo, Matias Korman, Carlos Seara, Rodrigo I. Silveira,