کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414616 680988 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex blocking and partial orders on the plane
ترجمه فارسی عنوان
مسدود کردن محدب و ترتیب های جزئی در صفحه
کلمات کلیدی
مسدود کردن محدب؛ ترتیب های جزئی؛ فضای دوگانه؛ گرافهای چندگانه؛ الگوریتم ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let C={c1,…,cn}C={c1,…,cn} be a collection of disjoint closed bounded convex sets in the plane. Suppose that one of them, say c1c1, represents a valuable object we want to uncover, and we are allowed to pick a direction α∈[0,2π)α∈[0,2π) along which we can translate (remove) the elements of C  , one at a time, while avoiding collisions. We study the problem of finding a direction α0α0 such that the number of elements that have to be removed along α0α0 before we can remove c1c1 is minimized. We prove that if we have the sorted set DD of directions defined by the tangents between pairs of elements of C  , we can find α0α0 in O(n2)O(n2) time. We also discuss the problem of sorting DD in o(n2log⁡n)o(n2log⁡n) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 51, January 2016, Pages 55–66
نویسندگان
, , , , , ,