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.
TitelProceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014
ErscheinungsortOttawa, Canada
Herausgeber (Verlag)Carleton University
PublikationsstatusVeröffentlicht - 08.2014
Veranstaltung26th Canadian Conference on Computational Geometry (CCCG) - Halifax, Kanada
Dauer: 11.08.201413.08.2014


Untersuchen Sie die Forschungsthemen von „On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals“. Zusammen bilden sie einen einzigartigen Fingerprint.