کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6868447 1439976 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two optimization problems for unit disks
ترجمه فارسی عنوان
دو مشکل بهینه سازی برای دیسک های واحد
کلمات کلیدی
کوتاهترین درخت مسیر، نمودار دیسک واحد نمودار هندسی، حداقل تفکیک، پیاده سازی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the minimum-separation problem, we are given n unit disks and two points s and t, not contained in any of the disks, and we want to compute the minimum number of disks one needs to retain so that any curve connecting s to t intersects some of the retained disks. We present a new algorithm solving this problem in O(n2log3⁡n) worst-case time and its implementation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volumes 70–71, February 2018, Pages 1-12
نویسندگان
, ,