Rectangulations

Short description: Discrete mathematics decomposition

A rectangulation of size 6, with all rectangles labeled in NW-SE order.

In discrete mathematics, a rectangulation (or mosaic floorplan) ${ℛ}$ is a decomposition of a rectangle into finitely many interior-disjoint rectangles. The size of a rectangulation describes the number of rectangles used in the decomposition. A segment $s$ of a rectangulation is a maximal straight line segment, which is not contained in a side of ${ℛ}$. The neighbors of a segment $s$ are those segments with an endpoint on $s.$ If no four rectangles meet in a point the rectangulation is called generic (or mosaic). Furthermore, every generic rectangulation of size $n$ has exactly $n-1$ segments. This article will consider every rectangulation to be generic, if not stated otherwise.

This topic is closely related to guillotine partitions and has applications in integrated circuit design, where floorplanning represents an early step in the design flow.

Definitions

Left-right and above-below order on rectangles

• A rectangle $r$ of the is to the left of a rectangle $\tilde{r}$ if there exists a sequence of rectangles $r=r_1,r_2,\dots ,r_k=\tilde{r}$, such that for $i=1,\dots ,k-1$ the right side of $r_i$ is contained in the same segment as the left side of $r_{i+1}$. In this case we equivalently say $\tilde{r}$ is to the right of $r$.
• A rectangle $r$ of the is above a rectangle $\tilde{r}$ if there exists a sequence of rectangles $r=r_1,r_2,\dots ,r_k=\tilde{r}$, such that for $i=1,\dots ,k-1$ the top side of $r_i$ is contained in the same segment as the bottom side of $r_{i+1}$. In this case we equivalently say $\tilde{r}$ is below $r$.

Using this order we can show that every pair distinct of rectangles satisfies exactly one of these relations.

Weak and strong equivalence

Four rectangulations of size 5. The rectangulations ${{ℛ}}_1,{{ℛ}}_3$ and ${{ℛ}}_4$ are weakly equivalent and the rectangulations ${{ℛ}}_1$ and ${{ℛ}}_3$ are strongly equivalent.

For two rectangulations ${{ℛ}}_1$ and ${{ℛ}}_2$ we define two types of equivalence:

• ${{ℛ}}_1$ and ${{ℛ}}_2$ are weakly equivalent, if there exists a (unique) bijection between the rectangles of ${{ℛ}}_1$ and ${{ℛ}}_2$ preserving the left-right and above-below orders.
• ${{ℛ}}_1$ and ${{ℛ}}_2$ are strongly equivalent, if they are weakly equivalent and the corresponding bijection between the rectangles also preserves adjacency between rectangles.

These relations define the weak and strong equivalence classes. The set of weak equivalence classes for rectangulations of size $n$ is denoted by ${\text{WR}}_n$ and elements of this set are called weak rectangulations. Analogously the set of strong equivalence classes for rectangulations of size $n$ is denoted by ${\text{SR}}_n$ and elements of this set are called strong rectangulations.

Labeling rectangles

The labeling of the rectangles of a rectangulation depends on the selected corner. Starting at one corner the rectangle labelled first, is the one containing that corner. Removing the labelled rectangle leaves a distinct segment that can be moved in order to restore the rectangles to a rectangulation. Again, the rectangle containing the selected corner is labelled and removed until a single rectangle remains. Since this article only considers mosaic rectangulations, the movable segment and therefore the labeling with respect to each corner is unique.

Labeled rectangles of a rectangulation starting at NW-corner(left) and starting at SW-corner(right).

Guillotine rectangulations

A guillotine rectangulation(left) and a non-guillotine rectangulation(right)

A rectangulation is called guillotine rectangulation if the segments can be ordered so that when the partition is executed according to that order, the current segment always partitions a rectangle into two rectangles.

Bijections to permutation classes

There are several known bijections between equivalence classes of rectangulations and permutation classes. In the following table $p_1$ and $p_2$ refer to the mesh patterns given by $p_1=(25314,\{(0,3),(0,4),(1,3),(4,2),(5,1),(5,2)\})$ and $p_2=(41352,\{(0,1),(0,2),(1,2),(4,3),(5,3),(5,4)\})$.

Table of bijections between rectangulations and permutations

Rectangulations	Permutations
Weak rectangulations	Baxter permutations, twisted Baxter permutations, co-twisted Baxter permutations
Weak guillotine rectangulations	separable permutations, $\{p_1,p_2\}$-avoiding twisted Baxter permutations, $\{p_1,p_2\}$-avoiding co-twisted Baxter permutations
Strong rectangulations	2-clumped permutations, co-2-clumped permutations
Strong guillotine rectangulations	$\{p_1,p_2\}$-avoiding 2-clumped permutations, $\{p_1,p_2\}$-avoiding co-2-clumped permutations

These bijections allow us to count the number of weak and strong rectangulations. For example, the number of weak rectangulations of size $n$ is therefore given by the $n$-th Baxter number (sequence A001181 in the OEIS), given by the formula:$$B_n=\sum _{k=1}^n\frac{(\genfrac{}{}{0ex}{}{n+1}{k-1})(\genfrac{}{}{0ex}{}{n+1}{k})(\genfrac{}{}{0ex}{}{n+1}{k+1})}{(\genfrac{}{}{0ex}{}{n+1}{0})(\genfrac{}{}{0ex}{}{n+1}{1})(\genfrac{}{}{0ex}{}{n+1}{2})}$$for which it is known that $B_n\sim \frac{2^{3n+5}}{n^4\pi \sqrt{3}}$. Similarly the number of weak guillotine rectangulations of size $n$ is given by the $n$-th Schröder number (sequence A006318 in the OEIS).

Estimates on the number of rectangulations on planar point sets

A pointset $P$ in a rectangle(left) with two different possible rectangulations constructed on the points. In the center a guillotine rectangulation is shown and on the right a non-guillotine rectangulation is shown.

Given a set $P$ of $n$ points within a rectangle $R$, a rectangulation on a point set $P$ in $R$ is a generic rectangulation of $R$ such that every point in $P$ lies on one segment.

Here, generic point sets are considered.

There are several known estimates as well as exact numbers for the number of rectangulations of planar point sets. That means, we fix a point set and consider the number of rectangulations on this point set.

Table of estimates on number of rectangulations on planar points sets

Constraint on point set or counted rectangulation	Estimate respectively exact number
None	at least $(n+1)$-th Baxter number
None	at most $20^n/(\genfrac{}{}{0ex}{}{n+4}{n})$
Only counting guillotine rectangulations	$n$-th Schröder number
Relative order of the points in $P$ form a separable permutation	$(n+1)$-th Baxter number

Binary search trees and rectangulations

In computer science, an approach to the dynamic optimality problem on online algorithms for binary search trees (BST) involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible to avoid rectangles with only two points on their boundary. In addition to the geometric model introduced by Demaine et al. (2009), the BST dynamic optimality problem admits an equivalent formulation in terms of rectangulations. This equivalence was established by Kozma and Saranurak (2016).

When a rectangulation is constrained by a set $P$ of points (no two sharing the same horizontal or vertical line), every point of $P$ must lie in the interior of exactly one segment.

Given an access sequence $X=(x_1,\dots ,x_n)$ with distinct keys, map it to the point set $\{(x_i,i):1\le i\le n\}$. The initial rectangulation state consists of vertical segments through every point of $X$, plus the boundary margins. A valid end state consists of only horizontal segments that together cover every point of $\{1,\dots ,n\}$ on the horizontal lines $y=1,\dots ,n$.

The Rectangulation problem asks for the minimum number of flips that transform the initial (all-vertical) state into any valid end (all-horizontal) state. A flip adds a new horizontal or vertical segment between two existing points and, if necessary, splits intersecting segments, while preserving the property that every interior point has degree at least 2 and that no two segments cross improperly (the “elbow-free” condition).

In this setup, the following polynomial-time equivalence (up to constant factor) can be proven:

Theorem (Rectangulation ↔ Satisfied Superset) — Any algorithm for the Rectangulation problem can be converted into an algorithm for the Satisfied Superset problem with cost O of the number of flips, and vice versa.

Together with the fact that any algorithm for the Satisfied Superset problem (minimum superset of the input points that admits a Manhattan path between every pair) can be converted into a BST algorithm whose cost is $\mathrm{\Theta }$ of the superset size, and vice versa, this leads to the correspondence between BSTs and rectangulations.

Consequently, the minimum cost of serving $X$ in the BST model is $\mathrm{\Theta }$ of the minimum number of flips needed to go from the all-vertical to the all-horizontal rectangulation constrained by the points of $X$.

This “flip view” reinterprets classic BST algorithms (Splay, Greedy, etc.) as particular flip strategies and yields new algorithmic perspectives: the sequence of flips builds the BST solution in an order dictated by the internal structure of the query sequence, and progress toward the all-horizontal target is measurable.

The model further connects (up to an additive $O(n)$ term) to the Tree Relaxation problem: starting from the treap on $X$ (with y-coordinates as priorities), repeatedly perform valid edge flips (reparenting a child to a neighboring sibling under certain conditions) until reaching the unique root-to-leaf path ordered by increasing y-coordinate. This relaxation view highlights progress via strictly decreasing total edge height or increasing total edge width.

Some additional remarks:

1. The flip diameter of rectangulations (maximum distance between any two rectangulations on the same point set under flip/rotate operations) is $\mathrm{\Theta }$ of the BST optimum for certain inputs.
2. The Small Manhattan Network optimum is a lower bound on the BST optimum, and the two quantities coincide asymptotically on many inputs (including random permutations and pattern-avoiding point sets).
3. Upper bounds (dynamic finger, working set, etc.) and heuristics for BSTs arise naturally from optimization measures on intermediate rectangulations or monotone trees (total edge length, total distance from root, etc.).

Quadrangulation

For a quadrangulation $Q$ is the separating decomposition an orientation and coloring of the edges with two colors such that:

• bipartition of $V$ of $Q$, such that for the two outer vertices $s,t$ all edges incident to $s$ are red ingoing and all edges incident to $t$ are blue ingoing edges.
• for all vertices $V\setminus \{s,t\}$ the incidents edges of the same color form an non-empty interval satisfying an orientation rule

A bookembedding of a quadrangulation(left) and the corresponding segment contact representation(right).

This separating decomposition of $Q$ induces a segment contact representation which is a Rectangulation. Therefore, we observe that all red edges (respectively, blue) of $Q$ produce a spanning tree with root $s$ (respectively, $t$). Then we find an closed simple curve through all vertices without $s,t$, which separates all red and blue edges, which yields a two-page book embedding, and this yields an alternative layout. This is a non crossing drawing of a plane tree $T$ such that vertices placed on x-axis and all edges embedded in the halfplane above or below and all neighbors of a vertex lay completely on the left or on the right. These layouts are in bijection to binary trees and if we merge $s$ with the first vertex and $t$ with the last we get a segment contact representation, which is a rectangulation.

Triangulation

The dual graph of a rectangulation is a triangulation of a 4-gon. On these graphs, we can put a transversal structure, which is an orientation and coloring of the inner edges with two colors such that the following two rules hold:

Rules for outer vertices(left) and inner vertices(right).

When we have such a structure we can investigate if some rectangulations are strong equivalent, because if they have the same transversal structure, then they have the same dual graph which means they have the same segment contact representation.

Rectangle-of-influence

We can use these structures to get a so-called rectangle-of-influence drawing. By the method with transversal structures we have exactly the same, but by the method with the Book embeddings we use a four coloring instead of a binary coloring to get two different Book embeddings, which yields to a closed rectangle-of-influence drawing.

Rectangulations in higher dimensions

Rectangulations in two dimensions are well known. There are some extensions of bijections between higher dimensional rectangulations and permutations and representations of planar graphs in three dimensions.

Bijections between higher dimensional rectangulations and $d$-permutations

Similar to bijections between rectangulations and permutation classes in the $2$-dimensional case, there is a bijection between $2^{d-1}$-floorplans and $d$-permutations. A $d$-permutation is a $d$-tuple of permutations. A $d$-floorplan is a partition of a $d$-dimensional box ($d$-box) into interior-disjoint $d$-boxes. The boxes of a generic $d$-floorplan can be labeled as described for the $2$-dimensional case.

The labeling of the boxes also describes a total order of the interior boxes with respect to a corner $q$. Considering $d$ different corners maps a $2^{d-1}$-floorplan to a $d$-permutation. To get a bijection, the corners have to be chosen in a specific way, e.g. choosing opposite corners results in the inverse permutation. For a mapping from $d$-permutations to $2^{d-1}$-floorplans $2^{d-1}$ partial orders are extracted from the permutations. The partial orders are described above for $2$-floorplans and can be extended to more dimensions. Given one partial order for each dimension the floorplan is fully determined. The $d$-permutations compatible with the bijection are Baxter-$d$-permutations.

Plattenbauten

A Plattenbau together with a plane drawing of its touching graph with rectangles and vertices colored such that the 3-colorability is shown.

Sets of interior-disjoint axis-aligned rectangles in space are called Plattenbauten. They are a generalization of axis-aligned segment contacts in two dimensions. The touching graph of a Plattenbau has one vertex for each rectangle, two vertices are connected by an edge, if the corresponding rectangles touch. It can be shown that every 3-colorable planar graph ist the touching graph of a generic Plattenbau. A Plattenbau $G=(V,E)$ is generic, if there are no coplanar rectangles. It has the following properties:

• chromatic number $\chi (G)\le 3$
• neighborhood $N(v)$ is planar $\mathrm{\forall }v\in V$
• the smallest dimension $d$ such that $G$ is an intersection graph of $d$-boxes is at most $3$.