Finding tailored partitions
John E. Hershberger, Subhash Suri · 1989
We consider the following problem: given a planar set of points S, a measure μ acting on S, and a pair of values μ1 and μ2, does there exist a bipartition S = S1 U S2 satisfying μ(Si) ≤ μi for i = 1,2? We present algorithms of complexity Ο(n log n) for several natural measures, including the diameter (set measure), the area, perimeter or diagonal of the smallest enclosing axes-parallel rectangle (rectangular measure), and the side length of the smallest enclosing axes-parallel square (square measure). The problem of partitioning S into k subsets, where k ≥ 3, is known to be NP-complete for many of these measures.