کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950778 1441039 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
New results on the coarseness of bicolored point sets
ترجمه فارسی عنوان
نتایج جدید بر روی براق بودن مجموعه های دو رنگه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let S be a set n points in general position in the plane. A 2-coloring of S is an assignment of one of two colors (red or blue) to each point of S. Recently, a parameter called coarseness was introduced by Bereg et al. (2013) [7]; it is a measure of how well blended a given 2-coloring of S is. Informally, the coarseness of a 2-coloring is high when S can be split into blocks, each with a large difference in its number of red and blue points. In this paper, we study two questions related to this parameter: Given a 2-coloring of S, can its coarseness be approximated to a constant factor in polynomial time? What is the minimum coarseness over all 2-colorings of S? For the first problem, we show that there exists a polynomial-time algorithm that for a given 2-coloring of S, approximates its coarseness to a constant ratio. For the second problem, we prove that every set of n points can be 2-colored such that its coarseness is at most O(n1/4log⁡n). We show that this bound is almost tight since there exist sets of n points such that every 2-coloring has coarseness at least Ω(n1/4).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 123, July 2017, Pages 1-7
نویسندگان
, , , ,