کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871312 | 1440183 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Practical and efficient algorithms for the geometric hitting set problem
ترجمه فارسی عنوان
الگوریتم های عملی و کارآمد برای مسئله مجموعه ای از هندسه هندسی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مجموعه های ضربه ای هندسی، الگوریتم های تقریبی، هندسه محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D. Recently Agarwal and Pan (2014) presented a near-linear time algorithm for the case where D consists of disks in the plane. The algorithm uses sophisticated geometric tools and data structures with large resulting constants. In this paper, we design a hitting-set algorithm for this case without the use of these data-structures, and present experimental evidence that our new algorithm has near-linear running time in practice, and computes hitting sets within 1.3-factor of the optimal hitting set. We further present dnet, a public source-code module that incorporates this improvement, enabling fast and efficient computation of small-sized hitting sets in practice.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 240, 11 May 2018, Pages 25-32
Journal: Discrete Applied Mathematics - Volume 240, 11 May 2018, Pages 25-32
نویسندگان
Norbert Bus, Nabil H. Mustafa, Saurabh Ray,