کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415653 | 681222 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Covering a bichromatic point set with two disjoint monochromatic disks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let P be a set of n points in the plane in general position such that its elements are colored red or blue. We study the problem of finding two disjoint disks DrDr and DbDb such that DrDr covers only red points, DbDb covers only blue points, and the number of elements of P contained in Dr∪DbDr∪Db is maximized. We prove that this problem can be solved in O(n11/3polylogn) time. We also present a randomized algorithm that with high probability returns a (1−ε)(1−ε)-approximation to the optimal solution in O(n4/3ε−6polylogn) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 3, April 2013, Pages 203–212
Journal: Computational Geometry - Volume 46, Issue 3, April 2013, Pages 203–212
نویسندگان
S. Cabello, J.M. Díaz-Báñez, P. Pérez-Lantero,