| dc.description.abstract | 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(n2 log2 n)-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. | |
