Relationships of the Representations
We summarize the relationships between the representations in this section. A mosaic floorplan example and a general floorplan example are also discussed in detail to show the relationships.
According to the definitions of the representations, we have four relationships between the sequence-pair (SP), the corner block list (CBL), the twin binary tree (TBT) and the O-Tree representations.
For further discussions, we first define the 90˚ rotation of a floorplan as follows:
Definition 90˚ rotation of a floorplan: We use F90 to denote the floorplan obtained by rotating floorplan F, 90 degrees counterclockwise.
The four relationships are as follows and summarized in Fig. 53.30.
1. Given a mosaic floorplan and its corresponding corner block list CB=(S, L, T), there exists a sequence pair SP = (S 1, S2) corresponding to the same floorplan such that the second sequence of SP is same as the sequence S of the corner block list.
2. Given a mosaic floorplan and its corresponding twin binary trees (τ + ,τ − ), there exists a sequence pair SP = (S 1, S2) corresponding to the same floorplan such that the first sequence of SP is the same as the node sequence of in-order traversal in tree τ +.
3. Given a mosaic floorplan and its corresponding twin binary trees TBT ( τ + ,τ − ), there exists an O-tree corresponding to the same floorplan such that τ − is iden- tical to the O-tree after the tree conversion from a binary tree to an ordered tree.
4. Given a mosaic floorplan F , and its corresponding twin binary trees TBT ( τ + ,τ − ), the node sequence of in-order traversal in tree τ + is identical to the sequence S in the corner block list CB=(S, L, T) of the floorplan F90.
A Mosaic Floorplan Example
Fig. 53.31 describes an example of a mosaic floorplan. We illustrate the four representations. The twin binary trees are marked with circles and crosses as shown in Fig. 53.31. Two SP s, SP1 and SP2, out of many possible choices, are described in the figure.
The in-order traversal of the τ + in the twin binary trees representation produces the sequence π(τ + ) = ABCDFE, which is same as the first sequence of SP1 and SP2. In Fig. 53.31, an O-tree representation is also given. Its binary tree representation is identical to the τ − of the twin binary trees after tree conversion. The corner block list representation is next to the O-tree representation in Fig. 53.31. Its sequence S=FADEBC is same as the second sequence of SP1.
Fig. 53.32 shows the 90˚ rotation of the mosaic floorplan in Fig. 53.31. The CB (S,L,T) representation of F90 has S = ABCDFE (Fig. 53.32.), which is identical to π(τ ), the order of the twin binary trees representation (τ +, τ − ) of the floorplan in Fig. 53.31.
A General Floorplan Example
Fig. 53.33 illustrates a general floorplan. Only the O-tree and the sequence pair are capable of representing this general floorplan. The O-tree and SP representations are shown in the figure.
