کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327193 | 680860 | 2012 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Coloring half-planes and bottomless rectangles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We prove lower and upper bounds for the chromatic number of certain hypergraphs defined by geometric regions. This problem has close relations to conflict-free colorings. One of the most interesting type of regions to consider for this problem is that of the axis-parallel rectangles. We completely solve the problem for a special case of them, for bottomless rectangles. We also give an almost complete answer for half-planes and pose several open problems. Moreover, we give efficient coloring algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 45, Issue 9, November 2012, Pages 495-507
Journal: Computational Geometry - Volume 45, Issue 9, November 2012, Pages 495-507
نویسندگان
Balázs Keszegh,