finding tailored partitions
We consider the following problem: given a planar set of points S , a measure &mgr; acting on S , and a pair of values &mgr; 1 and &mgr; 2, does there exist a bipartition S = S 1 U S 2 satisfying &mgr; ( S i ) ? &mgr; i for i = 1,2? We present algorithms of complexity &Ogr; ( 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.
partition point measurement values algorithm complexity log parallel completeness