کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949634 1440199 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing the coarseness with strips or boxes
ترجمه فارسی عنوان
محاسبه برابری با نوار ها یا جعبه ها
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Recently, the concept of coarseness was introduced as a measure of how blended a 2-colored point set S is. In the definition of this measure, a convex partition Π, that is, a partition of S into sets {S1,…,Sk} of S whose convex hulls are pairwise disjoint, is considered. The discrepancy of Π, denoted by d(S,Π), is the smallest (bichromatic) discrepancy of the elements of Π. The coarseness of S, denoted by C(S), is then defined as the maximum of d(S,Π) over all convex partitions Π of S. Roughly speaking, the value of the coarseness is high when we can split S into blocks, each with large discrepancy. It has been conjectured that computing the coarseness is NP-hard. In this paper, we study how to compute the coarseness for two constrained cases: (1) when the k elements of Π are separated by k−1 pairwise parallel lines (strips) and, (2) the case in which the cardinality of the partition is fixed and the elements of Π are covered by pairwise disjoint axis-aligned rectangles (boxes). For the first case we present an O(n2log2n)-time algorithm, and show that such a computation problem is 3SUM-hard; for the second, we show that computing the coarseness with k boxes is NP-hard, when k is part of the input. For k fixed, we show that the coarseness can be computed in O(n2k−1) time and propose more efficient algorithms for k=2,3,4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 224, 19 June 2017, Pages 80-90
نویسندگان
, , , ,