کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950778 | 1441039 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New results on the coarseness of bicolored point sets
ترجمه فارسی عنوان
نتایج جدید بر روی براق بودن مجموعه های دو رنگه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Information Processing Letters - Volume 123, July 2017, Pages 1-7
نویسندگان
J.M. DÃaz-Báñez, R. Fabila-Monroy, P. Pérez-Lantero, I. Ventura,