Feb 8, 2008

Problem: given a planar decomposition with weight w_i on each cell i, we would like to merge the cells to districts, such that each district is simply connected and the total weight is no greater than W. The objective is to minimize the number of districts. Additional considerations may require nice shapes for the districts (convex, etc).

Estie showed a reduction from Partition problem and proved the problem is weakly NP-hard.

Steve proposed a variation of the problem. Given a polygon with a triangular subdivision, merge the triangles to get convex pieces.

Joe reviewed results on Hertel Mehlhorn greedy algorithm and a 4-approximation proof.