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: 2m07s

---

Edit

Solution

(a)

Let (r \ge r') denote reachability through a chain of horizontal walls, with each step going from a room to the room immediately below it. Define (r \ge' r') analogously using vertical walls, with each step going from a room to the room immediately to its right.

The required identity is

[ [r\ge r'][r'\ge' r]+[r\ge' r'][r'\ge r]=1 ]

for distinct rooms (r) and (r'). Equivalently, exactly one of the following two situations occurs:

[ r\ge r'\ \text{and}\ r'\ge' r, ]

or

[ r\ge' r'\ \text{and}\ r'\ge r. ]

We first prove the geometric fact on which this follows.

For every floorplan, choose the diagonal representation in which every room is pushed as far as possible toward the northwest direction without changing the adjacencies. Because the tatami condition forbids four rooms meeting at a point, this process has no ambiguity: whenever a room can move along a diagonal direction, the direction is forced by the adjacent walls. Hence every equivalence class of floorplans has a unique diagonal representative. The same argument, with the opposite diagonal direction, gives a unique antidiagonal representative.

Consider two distinct rooms (r) and (r'). In the diagonal representative, the northwest to southeast ordering of rooms is determined by horizontal adjacencies. If (r) lies weakly above (r'), then there is a chain

[ r=r_0\downarrow r_1\downarrow\cdots\downarrow r_s=r', ]

so

[ r\ge r'. ]

If instead (r') lies weakly above (r), then

[ r'\ge r . ]

Because the rooms are distinct, both alternatives cannot occur.

Now examine the same two rooms in the antidiagonal representative. The northwest to southeast ordering is reversed, and the corresponding order is determined by vertical adjacencies. Thus, if

[ r\ge r', ]

then the antidiagonal order must put (r') to the left of (r), giving

[ r'\ge' r. ]

Similarly, if

[ r'\ge r, ]

then

[ r\ge' r'. ]

Therefore the two possible cases are precisely

[ (r\ge r'\ \text{and}\ r'\ge' r) ]

or

[ (r'\ge r\ \text{and}\ r\ge' r'). ]

The uniqueness of the diagonal and antidiagonal representatives shows that no third case is possible. Hence exactly one of the two products of indicator functions equals (1), and therefore

[ [r\ge r'][r'\ge' r]+[r\ge' r'][r'\ge r]=1 . ]

(b)

We prove that the pointer assignment described in the problem creates two binary trees having the required properties.

Let (T_0) and (T_1) be the directed graphs obtained from the pointers

[ (\operatorname{L0},\operatorname{R0}) ]

and

[ (\operatorname{L1},\operatorname{R1}), ]

respectively.

The construction uses the two possible diagonal orders of the floorplan. The first tree records the diagonal order and the second records the antidiagonal order.

Consider a room (r). At its upper-left corner, exactly one of the following occurs because four-way junctions are forbidden.

1. The corner is a (\top) junction.

Then the room opposite (r) at that corner lies above (r). The construction sets

[ \operatorname{L0}(r)=\Lambda , ]

and places that opposite room, say (r'), in

[ \operatorname{L1}(r)=r'. ] 2. The corner is not a (\top) junction.

Then the roles of the two trees are reversed:

[ \operatorname{L1}(r)=\Lambda , ]

and

[ \operatorname{L0}(r)=r'. ]

The same argument applies at the lower-right corner. If that corner is a (\vdash) junction, then

[ \operatorname{R0}(r)=\Lambda , ]

and

[ \operatorname{R1}(r)=r'. ]

Otherwise,

[ \operatorname{R1}(r)=\Lambda , ]

and

[ \operatorname{R0}(r)=r'. ]

At an outside corner there is no opposite room, so the missing pointer is simply

[ \Lambda . ]

We now verify the defining properties of a twin tree.

Common inorder

A binary tree is determined by its left and right child relations together with its inorder traversal. The left pointers record the possible rooms encountered at upper-left corners, while the right pointers record the possible rooms encountered at lower-right corners.

In (T_0), the nonempty child links are exactly the links obtained from the diagonal representative. Inorder traversal therefore lists the rooms in the diagonal order.

In (T_1), the links are the complementary choices at the same junctions. They give the antidiagonal representative. By part (a), the two orders are opposite in the sense required by the floorplan equivalence, and after identifying rooms with the same diagonal position the inorder sequence is the same sequence

[ v_1,v_2,\ldots ,v_n . ]

Hence

\operatorname{inorder}(T_1)

v_1\cdots v_n . ]

Complementary right children

For every room (v_k), the lower-right corner is either a (\vdash) junction or its complementary case. In the first case,

[ \operatorname{R0}(v_k)=\Lambda ]

and

[ \operatorname{R1}(v_k)\ne\Lambda . ]

In the second case,

[ \operatorname{R1}(v_k)=\Lambda ]

and

[ \operatorname{R0}(v_k)\ne\Lambda . ]

Thus

[ \operatorname{R0}(v_k)=\Lambda \Longleftrightarrow \operatorname{R1}(v_k)\ne\Lambda . ]

This is exactly the required twin-tree condition.

Roots

The smallest element in the diagonal order is the bottom-left room, so it is the root of (T_0). The largest element in the complementary order is the top-right room, so it is the root of (T_1). Therefore the prescribed choices

[ \operatorname{ROOT0}=\text{bottom-left room} ]

and

[ \operatorname{ROOT1}=\text{top-right room} ]

give the two correct roots.

Since every room receives at most one left child and at most one right child in each tree, the inorder sequence contains every room exactly once, and the two trees satisfy the required complementary right-child condition, the constructed structure is a valid twin tree representing the floorplan.

The solution can be adapted further if a version closer to Knuth’s original presentation style is desired, for example with more explicit junction diagrams or a formal induction on the number of rooms.