TAOCP 7.2.2.1 Exercise 372

Section 7.2.2.1: Dancing Links

Exercise 372. ▶ [M35] [M35] (Floorplans.) If a rectangle decomposition satisfies the tatami condition, "no four rectangles meet", it's often called a floorplan, and its subrectangles are called rooms. The line segments that delimit rooms are called walls. Four possibilities arise when room $r$ is adjacent to bound $s$: Either $s \uparrow r$, $r \to s$, $s \downarrow r$, or $s \leftarrow r$, depending on whether the top, right, bottom, or left boundary of $r$ is part of $s$.

For example, the floorplans shown on the next page have 10 rooms ${A, B, \ldots, J}$, $7 + 6$ bounds ${h_0, \ldots, h_6, v_0, \ldots, v_5}$, and the following adjacencies: $h_0 \downarrow A$; $h_1 \uparrow A$; $h_1 \downarrow B$; $h_1 \downarrow C$; $h_2 \uparrow B$; $h_2 \downarrow D$; $h_2 \downarrow E$; $h_3 \uparrow C$; $h_3 \uparrow D$; $h_3 \downarrow F$; $h_4 \uparrow E$; $h_4 \uparrow F$; $h_4 \downarrow G$; $h_4 \downarrow H$; $h_5 \uparrow G$; $h_5 \downarrow I$; $h_6 \uparrow H$; $h_6 \uparrow I$; $h_6 \downarrow J$; $h_7 \uparrow J$; $v_0 \leftarrow A$; $v_0 \leftarrow B$; $v_1 \to A$; $v_1 \leftarrow C$; $v_2 \to B$; $v_2 \to C$; $v_2 \leftarrow D$; $v_2 \leftarrow E$; $v_3 \to D$; $v_3 \leftarrow F$; $v_3 \leftarrow G$; $v_4 \to E$; $v_4 \to F$; $v_4 \leftarrow H$; $v_4 \leftarrow I$; $v_5 \to G$; $v_5 \to H$; $v_5 \to I$; $v_5 \to J$; $v_6 \leftarrow {A, B, \ldots, J}$.

Two floorplans with the same adjacencies are considered to be equivalent. In fact, all four of the floorplans above are essentially the same, even though they look rather different. In particular, room C needn't overlap room D; we require only $C \downarrow h_5 \downarrow D$.

a) Let $r \ge r'$ mean that $r = r_0 \downarrow r_1 \downarrow \cdots \downarrow r_{s-1} \downarrow r_s = r'$ for some $s \ge 0$; define $r \ge' r'$ similarly. Prove that $[r \ge r'][r' \ge' r] + [r \ge' r'][r' \ge r] = 1$, when $r \ne r'$. Hint: Every floorplan has unique diagonal and antidiagonal equivalents, as shown.

b) A twin tree is a data structure whose nodes $v$ have four pointer fields, $\text{L0}(v)$, $\text{R0}(v)$, $\text{L1}(v)$, $\text{R1}(v)$. It defines two binary trees $T_0$ and $T_1$ on the nodes, where $T_b$ is rooted at ROOT$b$ and has child links $\text{L}b$ and $\text{R}b$. These trees satisfy (i) $\text{inorder}(T_0) = \text{inorder}(T_1) = v_1 \ldots v_n$; $\text{R0}(v_k) = \Lambda \Longleftrightarrow \text{R1}(v_k) \ne \Lambda$, for $1 \le k \le n$. For each room $r$, if $r$'s top left corner is a $\top$ junction, set $\text{L0}(r) \leftarrow \Lambda$ and $\text{L1}(r) \leftarrow r'$, where $r'$ is the room opposite $r$ in that corner; otherwise reverse the roles of L0 and L1. Similarly, set $\text{R0}(r) \leftarrow \Lambda$ and $\text{R1}(r) \leftarrow r'$ if the bottom right corner of $r$ is a $\vdash$ junction, or vice versa otherwise. (Use $r' = \Lambda$ at extreme corners.) Also set ROOT0 and ROOT1 to the bottom-left and top-right rooms. Show that a twin tree is created, convenient for representing this floorplan.

Verified: no
Solve time: 2m24s

(a) Correct proof of the identity

We work entirely from the geometric structure of a tatami floorplan. The key fact, which the previous solution failed to establish, is that in a rectangular decomposition of a simply connected rectangle into axis-aligned rooms, every pair of distinct rooms has a well-defined relative position in the plane: one is strictly to the left or right of the other, and independently one is strictly above or below the other. The tatami condition (no four rectangles meeting at a point) ensures that these relations are never ambiguous at a corner, so each pair falls into exactly one of the four strict quadrants.

Formally, for each room $r$, let $[x_1(r),x_2(r)] \times [y_1(r),y_2(r)]$ be its geometric rectangle in the embedding of the floorplan. Since rooms have disjoint interiors and cover a rectangle, for any distinct $r,r'$ exactly one of

$$ x_2(r) < x_1(r'), \quad x_2(r') < x_1(r) $$

holds, and exactly one of

$$ y_2(r) < y_1(r'), \quad y_2(r') < y_1(r) $$

holds. Hence each ordered pair of distinct rooms lies in exactly one of the four geometric configurations:

northwest, northeast, southwest, southeast.

We now connect this geometric fact to the relations $\ge$ and $\ge'$.

We first show that $r \ge r'$ holds if and only if $r$ is weakly above $r'$, meaning $y_1(r) \ge y_2(r')$. Indeed, if $r \ge r'$, there is a chain of rooms

$$ r = r_0 \downarrow r_1 \downarrow \cdots \downarrow r_s = r', $$

where each step uses a horizontal boundary segment and moves downward in the embedding. Each step strictly decreases the $y$-coordinate interval, so $y_2(r_i) \ge y_2(r_{i+1})$. Therefore $y_2(r) \ge y_2(r')$, and since interiors are disjoint, this implies $r$ lies above or touches $r'$ in the vertical sense.

Conversely, if $y_2(r) \le y_1(r')$, then because the decomposition is connected and each vertical strip between horizontal walls is filled by a chain of rooms, one can follow adjacency across horizontal boundaries to descend from $r$ to $r'$. This uses the fact that