کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874178 | 1441027 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing balanced islands in two colored point sets in the plane
ترجمه فارسی عنوان
محاسبه جزایر متعادل در دو مجموعه نقاط رنگی در هواپیما
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بازنشستگی، جزایر، مجموعه های محدب، هندسه محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let S be a set of n points in general position in the plane, r of which are red and b of which are blue. In this paper we present algorithms to find convex sets containing a balanced number of red and blue points. We provide an O(n4) time algorithm that for a given αâ[0,12] finds a convex set containing exactly âαrâ red points and exactly âαbâ blue points of S. If âαrâ+âαbâ is not much larger than 13n, we improve the running time to O(nlogâ¡n). We also provide an O(n2logâ¡n) time algorithm to find a convex set containing exactly âr+12â red points and exactly âb+12â blue points of S, and show that balanced islands with more points do not always exist.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 135, July 2018, Pages 28-32
Journal: Information Processing Letters - Volume 135, July 2018, Pages 28-32
نویسندگان
Oswin Aichholzer, Nieves Atienza, José M. DÃaz-Báñez, Ruy Fabila-Monroy, David Flores-Peñaloza, Pablo Pérez-Lantero, Birgit Vogtenhuber, Jorge Urrutia,