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

Maciej Liskiewicz, Alexander Idelberger


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.
Original languageEnglish
Title of host publicationProceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014
Number of pages9
Place of PublicationOttawa, Canada
PublisherCarleton University
Publication date08.2014
Publication statusPublished - 08.2014
Event26th Canadian Conference on Computational Geometry (CCCG) - Halifax, Canada
Duration: 11.08.201413.08.2014


Dive into the research topics of 'On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals'. Together they form a unique fingerprint.

Cite this