Draft:Rectangulations

Definitions

Weak and strong equivalence

For two rectangulations ${\displaystyle {\mathcal {R}}_{1}}$ and ${\displaystyle {\mathcal {R}}_{2}}$ we define two types of equivalence:

• ${\displaystyle {\mathcal {R}}_{1}}$ and ${\displaystyle {\mathcal {R}}_{2}}$ are weakly equivalent, if there exists a (unique) bijection between the rectangles of ${\displaystyle {\mathcal {R}}_{1}}$ and ${\displaystyle {\mathcal {R}}_{2}}$ preserving the left-right and above-below orders.
• ${\displaystyle {\mathcal {R}}_{1}}$ and ${\displaystyle {\mathcal {R}}_{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 ${\displaystyle n}$ is denoted by ${\displaystyle {\text{WR}}_{n}}$ and elements of this set are called weak rectangulations. Analogously the set of strong equivalence classes for rectangulations of size ${\displaystyle n}$ is denoted by ${\displaystyle {\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.

Guillotine rectangulations

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.^[1][3][4] In the following table ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$ refer to the mesh patterns given by ${\displaystyle p_{1}=(25314,\{(0,3),(0,4),(1,3),(4,2),(5,1),(5,2)\})}$ and ${\displaystyle p_{2}=(41352,\{(0,1),(0,2),(1,2),(4,3),(5,3),(5,4)\})}$.

More information , ...

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, ${\displaystyle \{p_{1},p_{2}\}}$-avoiding twisted Baxter permutations, ${\displaystyle \{p_{1},p_{2}\}}$-avoiding co-twisted Baxter permutations
Strong rectangulations	2-clumped permutations, co-2-clumped permutations
Strong guillotine rectangulations	${\displaystyle \{p_{1},p_{2}\}}$-avoiding 2-clumped permutations, ${\displaystyle \{p_{1},p_{2}\}}$-avoiding co-2-clumped permutations

Close

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

Estimates on the number of rectangulations on planar point sets

Given a set ${\displaystyle P}$ of ${\displaystyle n}$ points within a rectangle ${\displaystyle R}$, a rectangulation on a point set ${\displaystyle P}$ in ${\displaystyle R}$ is a generic rectangulation of ${\displaystyle R}$ such that every point in ${\displaystyle 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.

More information at least ...

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 ${\displaystyle (n+1)}$-th Baxter number [6]
None	at most ${\displaystyle 20^{n}/{\binom {n+4}{n}}}$ [7]
Only counting guillotine rectangulations	${\displaystyle n}$-th Schröder number [7]
Relative order of the points in ${\displaystyle P}$ form a separable permutation	${\displaystyle (n+1)}$-th Baxter number [7]

Close

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).^[8]

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

Given an access sequence ${\displaystyle X=(x_{1},\dots ,x_{n})}$ with distinct keys, map it to the point set ${\displaystyle \{(x_{i},i):1\leq i\leq n\}}$. The initial rectangulation state consists of vertical segments through every point of ${\displaystyle X}$, plus the boundary margins. A valid end state consists of only horizontal segments that together cover every point of ${\displaystyle \{1,\dots ,n\}}$ on the horizontal lines ${\displaystyle 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:

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 ${\displaystyle \Theta }$ of the superset size, and vice versa, this leads to the correspondence between BSTs and rectangulations.

Consequently, the minimum cost of serving ${\displaystyle X}$ in the BST model is ${\displaystyle \Theta }$ of the minimum number of flips needed to go from the all-vertical to the all-horizontal rectangulation constrained by the points of ${\displaystyle 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 ${\displaystyle O(n)}$ term) to the Tree Relaxation problem: starting from the treap on ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle Q}$ is the separating decomposition an orientation and coloring of the edges with two colors such that:

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

This separating decomposition of ${\displaystyle Q}$ induces a segment contact representation which is a Rectangulation. Therefore, we observe that all red edges (respectively, blue) of ${\displaystyle Q}$ produce a spanning tree with root ${\displaystyle s}$ (respectively, ${\displaystyle t}$). Then we find an closed simple curve through all vertices without ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle s}$ with the first vertex and ${\displaystyle 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:

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.^[9][10]

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.

Plattenbauten

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 ${\displaystyle G=(V,E)}$ is generic, if there are no coplanar rectangles. It has the following properties:^[12]

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

References