Home > Uncategorized > Optimal partitioning of a square into rectangles

Optimal partitioning of a square into rectangles


Problem. Which partition of the square into rectangles of equal areas minimizes the total perimeter of the cells?

The answer was given by T. Y. Kong, David M. Mount, and Michael Werman in the article The decomposition of a square into rectangles of minimal perimeter (Discrete Appl. Math., 16(3):239-243, 1987). The proof is quite interesting and it uses Dilworth’s theorem in an unexpected way. It turns out that the optimal partition can be described exactly by the following parameters.

If the number of rectangles, denoted {p} is a perfect square, then the natural candidate partition is the decomposition of the square into {p} smaller equal squares. Suppose now that {n^2<p<(n+1)^2}. We have two cases:

  • If {p \leq n(n+1)} then let {r = n(n+1)-p} and {s = p-n^2}.
  • If {p> n(n+1)} then let {r = (n+1)^2-p} and {s = p-n(n+1)}.

It is not hard to see that in either of the above cases we have {rn + s(n+1)=p}. The optimal partition is given by dividing the square into {r } rows of {n} rectangles with sides {(1/n,n/p)} followed by {s} rows consisting of {n+1} rectangles with sidelengths {(1/(n+1),(n+1)/p)}.

This problem came to my interest as a test case in some numerical computations. I wanted to find numerically the partitions which minimize the perimeter while the sets of their boundaries have two favorized directions: the vertical and the horizontal directions. This corresponds to minimizing the sum of some anisotropic perimeters of the cells (anisotropic = something which is not the same for every direction). For an introduction to the notion of anisotropic perimeters, you can consult this link.

The problem mentioned above is slightly more general than the initial problem concerning the rectangles. The idea is that we do not impose the fact that every region needs to be rectangular. We already know that if we search for optimal partitions which minimize the sum of the perimeters, the optimal results will not be rectangular partitions. For more details you can consult this link.

Searching numerically for optimal partitions can be challenging in multiple ways. First, in order to compute the perimeter of a set {\Omega} in a precise manner, a good description of the boundary {\partial \Omega} is needed. If we decide to follow this parametric formulation, then the partition condition, i.e. the fact that the cells do not overlap and cover the entire domain, is difficult to manage.

In order to avoid the above problem, one may try to find a way to transform the shape optimization problem into a functional problem. This can be done with the aid of a concept called {\Gamma}-convergence, which was recalled in some previous posts. We use again a reformulation of a classical result due to Modica and Mortola to find our approximation. Thus, in order to approximate a minimizer of the sum of anisotropic perimeters

\displaystyle \sum_{i=1}^n \text{Per}_\varphi(\Omega_i)]

we search for a minimizer of the functional

\displaystyle \sum_{i=1}^n \left( \varepsilon\int_D \varphi(\nabla u_i)^2+\frac{1}{\varepsilon} \int_D u_i^2(1-u_i)^2\right),

where the functions {u_i} satisfy the measure constraint {\int_D u_i = |D|/n} and the partition condition is simply {\sum_{i=1}^n u_i = 1}. It is straightforward to approximate all the above quantities on a finite element grid and perform a gradient descent procedure in order to find numerical minimizers. Below you can see a few of the results I obtained, together with a comparation to the isotropic case. The full details of this procedure as well as a complete sets of results will be contained in a forthcoming paper. In the meanwhile, you can consult this link for a more complete presentation.

I will present the proof of the initial theorem, which is interesting in itself, in some future posts.

anihv5 anihv5 anihv5 anihv5 anihv5
anihv5 anihv5 anihv5 anihv5 anihv5
Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: