On the Computational Complexity of Partitioning …

1 CCCG 2014, Halifax, Nova Scotia, August 11 13, 2014. On the Computational Complexity of Partitioning weighted Points into a Grid of Quadrilaterals Alexander Idelberger Maciej Li skiewicz . Abstract equal to the corresponding desired value. If such a Partitioning does not exist, a solution minimizing some In the paper the Computational Complexity of the follow- objective function is required. To express the initial ing Partitioning problem is studied: Given a rectangle Partitioning problem in this setting,Pone needs to define R in the plane, a set Q of positive- weighted points in each reference value equal to n11 n2 q Q (q), where . R, and two positive integers n1 , n2 , find a Partitioning denotes the weight function.

2 Of R into quadrilaterals whose dual graph is an n1 n2 The above problem is a natural generalization of the grid such that each quadrilateral contains points of equal well-studied 1-dimensional case: given a set of m positive- total weight. If such a Partitioning does not exist, find weighted points Q in an interval [0, a] R, an integer n, a solution that minimizes some objective function. This and a reference vector of size n, find a Partitioning of the problem is motivated by applications in image process- interval into n subintervals [0, x1 ), [x1 , x2 ), .. , [xn 1 , a]. ing including, among others, image enhancement and which minimizes some objective function.]]

3 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. (a) Input: a set of points (b) Output: an optimal in square [0, 1] [0, 1] and Partitioning into 3 3. integers n1 = n2 = 3. quadrilateral faces. 1 Introduction Figure 1: A points set with a unit weight assigned to any We study the following geometric problem to which point.

4 The task is to partition the square (a) into 3 3. we refer as q-grid Partitioning : For a given rectangle quadrilateral faces each containing the same number of R = [0, a] [0, b] in the plane, a finite set of positive- points. Figure (b) shows an optimal solution. weighted points Q = {q1 , .. , qm } in R, and two positive integers n1 and n2 , find a Partitioning of the rectangle R. into n1 n2 quadrilateral faces whose dual graph is an n1 n2 grid such that each face contains points of equal Motivation total weight. Particularly, if to each point in Q we assign Our study is motivated by applications in image process- a unit weight, every quadrilateral face should contain the ing, including image enhancement one of the central same number of points.

5 If such a Partitioning does not problems in image processing (see [7]). Basic, well- exist, the task is to find a solution, among possibly many, known image enhancement techniques are histogram that minimizes some objective function. Figure 1 shows equalization and histogram specification. an example instance of the problem and an optimal A histogram of an image in a d dimensional color space solution. can be represented by a weighted point set Q [0, a]d , In a more general setting of the problem, which we call with (q) describing the number of pixels of a color q. q-grid Partitioning with a reference table, we are given, in the RGB color space each color is represented by besides weighted points Q in [0, a] [0, b], a 2-dimensional a vector with three components Red, Green, and Blue n1 n2 table of non-negative desired reference weights.

6 And it is a point in the unit cube [0, 1]3 . Then the task is to partition the rectangle into n1 n2 The grey-scale histogram equalization problem is for- quadrilateral faces each containing points of total weight mulated as the 1-dimensional Partitioning problem with 1 2. P. Institute for Theoretical Computer Science, Universit . at zu the sample variance n (s i i ) or the average absolute 1. P. L . ubeck, deviation n i |si | as objective functions. Here, si 26th Canadian Conference on Computational Geometry, 2014. denotesP the total weight of points in the i-th interval and the conclusions of [11], Kundu claims that the problem = n1 q Q (q). The grey-scale histogram specifica- can be formulated as shortest path problem and solved tion can be expressed as 1-dimensional Partitioning with efficiently.

7 Later [12], he observes that the problem is reference vector r1 , r2 , .. , rn that represents a desired much more difficult than the 1-dimensional case and that histogram. the suggested approach does not work. Histogram equalization for color images becomes a much more difficult challenge because of the multidi- Our Contribution mensional nature of color. The difficulty of the problem arises due to the correlation between the color compo- In this paper we prove that a decision version of the nents as well as the Complexity of the human perception. Partitioning problem is NP-hard: given a set of weighted The research in image processing led to the develop- points Q = {q1.}

8 , qm } in a rectangle R = [0, a] [0, b]. ment of two main classes of algorithms: the first one and two positive integers n1 , n2 , find an n1 n2 q- operating in the RGB space and the second one oper- grid Partitioning of R minimizing the deviation in the ating in nonlinear color spaces (for more details see maximum-norm. Moreover, we show that the prob- [1, 5, 9, 14, 16, 18]). The Complexity questions studied lem is NP-hard also for some other important objective in this paper concern algorithmic problems representing functions. We show that the problem remains NP-hard colors in linear spaces. even if Q contains points of integer coordinates, if The most straightforward extension of grey-scale his- Q [0, a] [0, b] N2.

9 To prove these results we show a togram equalization to color images is to apply it for polynomial time reduction from the planar version of the each color band separately, obtaining an orthogonal grid. 1-In-3-SAT problem, which is known to be NP-hard [13]. However, since this approach ignores the correlation be- We leave as an open question if the Partitioning prob- tween the color components, it is not suitable for color lems are in NP. We conjecture an affirmative answer. enhancement and related tasks. Using an orthogonal The main difficulty in proving this is to show that there grid and taking the correlation into account results in must exist an optimal q-grid Partitioning the coordinates the modeling (discussed in more detail below) analyzed of which have bounded precision, such that their by Grigni and Manne [8].

10 The more appropriate exten- representations have polynomial size with respect to the sion, proposed by Pichon et al. [16], initially partitions total size of the input. the color space of the image histogram Q into cells of a scaled regular mesh. Then the mesh is iteratively de- Related Results formed minimizing the absolute deviation. Mapping the cells of the deformed mesh to the corresponding cells of Recently, Evans et al. introduced in [6] the concept of a regular mesh yields the color transformation. Thus, table cartogram a new model of 2-dimensional car- the method generates an almost uniform color histogram togram. The input of the table cartogram is an n1 n2.