On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals

In the paper the computational complexity of the following partitioning problem is studied: Given a rectangle R in the plane, a set Q of positive-weighted points in R, and two positive integers n1, n2, find a partitioning of R into quadrilaterals whose dual graph is an n1 × n2 grid such that each quadrilateral contains points of equal total weight. If such a partitioning does not exist, find a solution that minimizes some objective function. This problem is motivated by applications in image processing including, among others, image enhancement and similarity retrieval, and it is closely related to the table cartogram problem introduced recently by Evans et al. [ESA 2013]. While there exist fast algorithms that find optimal partitions in 1-dimension, the 2-dimensional case seems to be much harder to solve. Pichon et al. [ICIP 2003] proposed a heuristic yielding admissible solutions, but the computational complexity of the problem has so far remained open. In this paper we prove that a decision version of the problem is NP-hard.