Scalene rectangulation of a square: let me count the ways

Question

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles $R_i,R_j$ are disjoint.

We say a rectangulation is scalene if distinct rectangles (including the square $S$) do not have equal length sides of either parallel or perpendicular orientation.

Here is a square dissected into five smaller rectangles:

Figure 1: Scalene rectangulation layout for five rectangles

By a bit of perturbation in both axes separately, we can doubtless arrange none of the rectangles will have equal length sides. Up to the dihedral symmetries of a square and such axis-wise homotopy, this layout is unique (in allowing a scalene rectangulation of a square into five rectangles).

I am motivated by this previous Question to ask if the following layout using seven rectangles is similarly unique:

Figure 2: Scalene rectangulation layout for seven rectangles

More generally I am curious to count the scalene rectangulation layouts possible for each $n \ge 5$ (there are none for smaller $n$). I would like an algorithm that, given $n$, generates all the possible layouts for scalene rectangulation of a square into $n$ smaller rectangles. If the algorithm did not perfectly eliminate all redundancy, but still reduced the possible layouts to a manageable number, this would be an advance over my present understanding.

[To provide more context I will follow up this Question with a CW "answer" that summarizes what I've been able to glean from the literature and my own investigations.]

Answer 1

We give a discrete combinatorial approach to the above problem, counting scalene rectangulations "up to equivalence". This may clarify the notion of equivalent rectangulations and encourage others to use this approach.

As a planar graph, a scalene rectangulation with $r$ sub-rectangles has $r+1$ "faces" in the sense of Euler's famous equation:

$$ V + F = E + 2 $$

because the exterior region is considered a face. As each sub-rectangle has a left and a right edge (also a bottom and a top edge), it is convenient to view the edges of the exterior similarly but reversed. That is, the extreme left edge is considered the exterior face's nominal "right" edge, abutting left edges of interior rectangles, and a similar convention is made with respect to the extreme right, lower, and upper edges of the subdivided rectangle.

With this convention we can present the basic idea of discretizing our problem, namely to identify the vertical and horizontal lines that contain edges of the $r+1$ rectangles. The idea is that two different rectangles cannot share their left and right "gridlines" that extend their vertical boundaries, and similarly for different rectangles and their bottom and top boundaries, because that will imply equal widths or heights respectively.

Generically we can think of the vertical gridlines, each of which contains some left or right edge of a rectangle, as ordered $x = x_0, x_1, \ldots, x_m$ with:

$$ x_0 \lt x_1 \lt \ldots \lt x_m $$

Thus there are $m$ horizontal gaps between $m+1$ vertical lines (fence posts!). Similarly there are a finite number of horizontal gridlines $y = y_0, y_1, \ldots, y_n$ with:

$$ y_0 \lt y_1 \lt \ldots \lt y_n $$

which cover all the bottom and top edges of rectangles. Note that we eschew any extraneous horizontal gridlines, those not containing any bottom or top edge.

Now any scalene rectangulation gives rise to a partition where no two different rectangles share either a common pair of vertical boundaries or of horizontal boundaries. Moreover, if we have a partition where no distinct rectangles share either vertical or horizontal boundaries, then by a perturbation of gridlines we obtain a scalene rectangulation, i.e. where no widths or heights of rectangles are shared by different rectangles.

Based on this observation, we define an equivalence on rectangulations which gives for any fixed number $r$ of rectangles a finite number of equivalence classes. Two rectangulations are equivalent iff they can be matched by a finite chain of the following two kinds of operations:

1. There exist monotone real mappings $f,g$ which respectively applied to vertical and horizontal gridlines of two rectangulations matches their rectangles.

2. There exists a dihedral symmetry which matches their rectangles.

[Note that a small overlap exits between these two kinds of operations because if (1) $f,g$ are allowed to be monotone decreasing, we can get the left/right and bottom/top reversals in (2). What (2) provides apart from (1) are rotations.]

Now the above chain of operations does allow scalene rectangulations to be equivalent to non-scalene rectangulations, i.e. ones in which widths or heights happen to be duplicated "by accident" of gridline spacings. However by perturbation of gridlines the scalene property can be recovered, as discussed above. Thus the discrete problem is posed as follows:

Problem Let $\mathscr S = [0,\ldots,m]\times [0,\ldots,n]$. Choose $r$ pairs of points $(i,j),(k,\ell) \in \mathscr S$ with $i\lt k$ and $j\lt \ell$ such that:

(i) the $r$ rectangles $[i,k]\times [j,\ell]$ cover $[0,m]\times [0,n]$ and have pairwise disjoint interiors,
(ii) each horizontal coordinate and each vertical coordinate appears at least once,
(iii) no two rectangles share the same horizontal interval $[i,k]$ nor the same vertical interval $[j,\ell]$, and
(iv) no rectangle has horizontal interval $[0,m]$ or vertical interval $[0,n]$.

We can quickly sketch an algorithm to find all solutions, up to equivalence, for fixed $r,m,n$. Choose $r$ distinct pairs $(i,j)\in [0,\ldots,m]^2, i\lt j$ and match them to distinct pairs $(k,\ell) \in [0,\ldots,n]^2, k\lt \ell$ in a way that satisfies the above restrictions. Some additional remarks on checking those restrictions will occur below, including elimination of equivalent solutions by symmetries. However there are clearly only a finite number of solutions for fixed $r,m,n$.

Indeed there are only a finite number of solutions for fixed $r$, regardless of restrictions on grid size $m\times n$. We need only show that a fixed $r$ admits only a finite number of feasible $m,n$. As the roles of $m,n$ are interchangeable, we state the following result with respect to $m$, and note that it remains equally true when $m$ is replaced by $n$.

Prop. 1 Let $r$ be the number of rectangles in the problem above. If we include the exterior rectangle, each vertical gridline must have at least three left or right edges of rectangles on it.

Proof: By construction at least one of the $r$ rectangles has either a left or a right edge on a specified vertical gridline. Those rectangles are not allowed to take up the entire vertical height (that would duplicate the height of the exterior rectangle), and a left or right edge must face a portion of a right or left edge on the other side of the gridline. Finally those two opposing edges cannot be equal intervals, so at least one must be adjacent to a third edge on its same side of the gridline.

Cor. 1 With $r,m$ as above, $$ 3(m+1) \le 2(r+1) \le m(m+1) $$

Proof: Counting the left and right edges of the combined interior and exterior rectangles, we have $2(r+1)$. The left hand inequality then follows immediately from Prop. 1 (each of the $m+1$ gridlines has at least three such edges). The right hand inequality follows from the $r$ distinct horizontal intervals of interior rectangles (distinct as well from the width of the exterior rectangle):

$$ r \le \binom{m+1}{2} - 1 $$

Finally the double inequality above can be solved for bounds on positive integer $m$ in terms of $r$:

Cor. 2 With $r,m$ as above, $$ \left\lceil \frac{\sqrt{8r+9} - 1}{2} \right\rceil \le m \le \left\lfloor \frac{2r-1}{3} \right\rfloor $$

Proof: Left as an exercise for the Reader in completing the square.

Thus for fixed $r$, we have a finite range of feasible horizontal widths $m$ and also of feasible vertical heights $n$ in the discrete combinatorial Problem. Some examples of applying this to counting equivalence classes of solutions will follow.

Answer 2

At least five rectangles are needed

One implication of a rectangulation being scalene is that two rectangles cannot meet exactly in a common side, i.e. not face-to-face as in a typical rectangular mesh generation (e.g. for finite elements).

Moreover the smaller rectangles cannot completely cover a side of the square $S$, so that each side of $S$ must include a vertex, a corner of a smaller rectangle. Thus the rectangles that cover the corners of the square must be distinct, giving a lower bound of four rectangles needed.

We can improve this to a minimum of five rectangles with the following:

Lemma If a rectangle $Q$ is dissected into:

• 2 smaller rectangles, then each has a side in common with $Q$ and also one between themselves.
• 3 smaller rectangles, then one has a side in common with $Q$, and the other two have a common side between themselves.
• 4 smaller rectangles, each has either a side in common with $Q$ or one with another of the smaller rectangles.

Proof: The first two propositions are fairly evident.

For the last, if one of the four smaller rectangles $R$ shares a side with $Q$, the other three rectangles dissect $Q\setminus R$ and we can rely on the early parts of this lemma. Otherwise none of the four smaller rectangles share a side with $Q$, and thus each covers exactly one corner of $Q$.

Fix any smaller rectangle $R = \overline{ABCD}$ (its corners in cyclic order), where $A$ is also a corner of $Q$. Let $S$ be the rectangle bordering $R$ at $B$, and let $T$ be the rectangle bordering $R$ at $D$.

The exterior angle of $R$ at $C$ is reflexive, so there must be at least two rectangles adjacent to $R$ at $C$ (by convexity). At least one of $S$ and $T$ must then be adjacent to $R$ at $C$ (by counting). $S$ and $T$ cannot both extend past $C$ without overlapping, and if either $S$ or $T$ terminates at $C$ then that rectangle would share a side with $R$.

That leaves the case that (say) $S$ is not adjacent to $R$ at $C$ and $T$ extends beyond $R$ at $C$. Since $S$ and $T$ would not be adjacent, the fourth smaller rectangle $U$ would need to fill that gap and thus $U$ be adjacent to $R$ at $C$. But then neither $S$ nor $U$ can block $T$ from extending past $C$ all the way to share a side with $Q$. Contradiction. █

With a bit of care we can read into this proof the conclusion that such a scalene layout of five rectangles is unique up to equivalence. However the seeming ad hoc presentation of geometric considerations make it an undesirable model for pursuing cases with even modestly more rectangles.

For example, I conjecture that there are no layouts with six rectangles, and that the layout with seven rectangles already illustrated is similarly unique. Ideally we will find a way to "arithmetize" our search for layouts, allowing for discrete algorithms to efficiently determine existence and uniqueness.

Casting a wide C-net

Many Readers will have noticed that these layouts define a planar graph whose vertices are shared corners of rectangles and whose edges are portions of a rectangle's boundary connecting two such vertices. Much investigation has been made of planar graphs whose "faces" (including the exterior face of a planar graph) can be realized as convex polygons bounding a polyhedron. It is not hard to see their (planar) duals are again of this kind.

In the literature on counting distinct polyhedral graphs (Duijvestijn and Federico, 1981; Duijvestijn, 1996), such a graph is often referred to as a $C$-net in respect of the combinatorial characterization of polyhedral graphs as $3$-vertex-connected planar graphs. The term order of a $C$-net is used to mean the number of edges.

Study of these stretches back to Euler's 1750 paper, "Elementa doctrinae solidorum," where he classified convex polyhedra according to Euler's famous formula:

$$ v + f = e + 2 $$

relating the numbers $v,f,e$ of vertices, faces, and edges. Our case is $f=8$ (octahedra), and the counts of possible $C$-nets (generically, without our geometric restrictions to rectangles with unequal sides) were known to Kirkman (1862):

Table 1. $C$-nets with eight faces

vertices    edges(order)     # of c-nets
    6            12                2
    7            13               11  
    8            14               42  
    9            15               74  
   10            16               76  
   11            17               38  
   12            18               14