کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415653 681222 2013 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Covering a bichromatic point set with two disjoint monochromatic disks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Covering a bichromatic point set with two disjoint monochromatic disks
چکیده انگلیسی

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
نویسندگان
, , ,