# The equivalence of the subregion representation and the wall representation for a certain class of rectangular dissections.

The Equivalence of the Subregion Representation and the Wall Representation for a Certain Class of Rectangular Dissections

1. INTRODUCTION A rectangular dissection is a partition of a rectangular space R into n [is not >] 1 disjoint rectangles [r1, r2,..., rn], that are called the basic regions. The number of basic regions in a dissection is called the order of that dissection. A dissection D is called a T-plan [6] if each junction point where a vertical line meets with a horizontal line is a T-junction. A T-plan is a model for space partitioning in VLSI design [10, 15] and floor-space planning in architectural design [2-9, 11-14, 16-18). Here R represents the total design space and each n represents a room in the floor-plan and a macro-circuit in the VLSI-placement. Figure 1(a) shows a T-plan of order 9. We assume that the top and the bottom edge of the rectangle R of a dissection extends to the left and to the right as indicated in the figure by broken lines. We do not often show these broken lines explicitly, however. The regions outside R are labeled W, E, N, and S, and are called the external regions. A dissection D that is not a T-plan can be replaced by a suitable T-plan provided we regard two junction points of a T-plan to be coincident if they are sufficiently close (i.e., their distance is below a certain threshold c > 0 [6]). This is illustrated in Figure 1(b).

A design problem, in general, has associated with it two classes of constraints: The topological constraints that specify the horizontal and vertical adjacencies between the r.sub.i.s, and the nontopological or dimensional constraints that specify bounds on the area, length, and width and so forth, of the r.sub.i.s. In addition to finding a feasible dissection D that meets the given topological and dimensional constraints, one is typically interested in optimizing a certain objective function that can be associated with D. For example, one may want to minimize the total length of the partitioning walls, minimize the largest ratio between the length and width of a rectangle, maximize the smallest length (>c) of the common wall between two adjacent rectangles, and so on. The best known approach to solve the optimal dissection problem is at present a two-phase process: (1) Obtain, all, or as many as possible topologically distinct feasible configurations that meet the adjacency requirements of the r.sub.i.s [4, 6-9], and (2) for each of these feasible configurations, determine the additional dependent constraints (such as the relationships among the lengths of rectangles that share a common wall, see [6]), and then find the optimal dissection for that configuration using the dependent constraints and the given dimensional constraints [2, 16]. There is often a third and final phase in which one selects one of the best layouts obtained in phase (2) based on considerations of aesthetics and other characteristics which are difficult to quantify [17].

As has been pointed out in [7], the difficulty of using the above two-phase method is that often the topological constraints in the design problem are too few (i.e., the design problem is underspecified), which leads to too many topologically feasible configurations to be considered in the second phase. The alternative suggested in [7] is that one should first obtain a "higher" level abstraction of the design problem and evaluate the solutions of the abstract version first. The main idea behind this approach is that, depending on the level of abstraction, there would be fewer possible configurations to consider. One can then focus more closely on those configurations that look promising and analyze them in further detail in the next lower level of abstraction, and so on, finally generating the required (optimal or "nearly" optimal) solutions. In this process, one eliminates as many dissections as possible at the earliest stages. Although this approach has its own share of difficulties, as listed below in (a)-(b), the notion of using some kind of abstraction method to limit the combinatorial complexity of possible configurations seems unavoidable. The difficulty of using abstractions are:

(1) Finding a good abstraction mechanism. One typically would need several classes of abstraction mechanisms so that one can select an abstraction scheme based on the form and volume of the given constraints. The abstraction which captures the designer's primary constraints would be considered first.

(2) Transforming the given constraints for the total design into the constraints for the abstracted version of the problem. Indeed, without such a transformation in hand, it would not be possible to optimize the abstraction and determine which abstracted form should be selected for detailed analyses.

The three major abstraction mechanisms that are presently known are: (i) the wall representation [6], (ii) the graph representation [6, 16], and (iii) the [delta]-transform [7]. These abstractions are, however, mostly suitable for classifying known solutions or layouts. They do not allow a convenient transformation (as required in (2)) of a design problem so that the latter may be reformulated and reduced in size (the number of topological and dimensional constraints, the number of basic rectangles, etc.) to make it easier to solve. The [delta]-transform satisfies some of these requirements but has the problem that it may convert a T-plan to a non-T-plan, in general.

There is yet a third abstraction method based on the notion of a subregion. A subregion of a dissection D is a rectangular subspace of R that is the union of one or more basic regions r.sub.i D. In general, a T-plan may not have any non-trivial subregions other than R and the r.sub.i.s. The subregions of a T-plan D form of a tree structure, called the subregion representation of D; the root node of this tree corresponds to the whole design space R. The subregion abstraction is briefly mentioned in [10] for a subclass of T-plans, called T*-plans, but no formal theory has been developed. The main contribution of this paper is to show that the subregion representation of T*-plans is equivalent to their wall representations [6]. The conversion from the subregion representation to the wall representation is relatively simple and is given in Theorem 1. The rest of this paper deals with the conversion from the wall representation to the subregion representation. The final conversion algorithm is given in A.sub.3.. The alogrithm A.sub.3 takes at most O(n.sup.2.) time, where n is the order of the T*-plan. The implementation techniques developed for the algorithm A.sub.1 (for classiying the walls in the wall representation) is used in both algorithms A.sub.2 and A.sub.3 with suitable modifications. In [12, 13], we present several other important properties of T*-plans. These results make us believe that the subregion abstraction scheme will prove to be an effective tool in determining optimal dissections. The subregion representation also appears to have some of the characteristics mentioned in (1)-(2) in this section, but they need to be studied and developed further and are not addressed here.

2. THE T*-PLANS

A T-plan is called a T*-plan if it is obtained by repeated application of the following four partitioning operations starting with the rectangle R: (1) the horizontal partitioning; (2) the vertical partitioning; (3) the left-spiral partitioning, and; (4) the right-spiral partitioning. Figure 2 shows these partitioning operations and the structure of the associated subregion trees. A horizontal or vertical partitioning operation of order k [is greater than or =] 2 decomposes a rectangle into k subrectangles, and the left-and the right-spiral partitions decompose a rectangle into five subrectangles. We refer to these partitioning operations in short as h-, v-, s-, and S-partitions. The h- and the v-partitions differ by 90[deg.] rotation, and the s- and the S-partitions differ by a reflection (The reflection of the s-partition gives the S-partition, and vice versa). It is worth noting that the wall-transformations described in Figure 9(a)-(c) in [6] correspond to the v-partition, and a special case of that in Figure 9(d) of [6] gives the S-partition. Figure 16 in [6] contains four T-plans (items 4, 11, 18, and 19) which are not T*-plans; each of them are variations of a double spiral. We denote a subregion by the set of basic regions contained in it. In Figure 1(a), [left brace]r.sub.6., r.sub.7.[right brace], [left brace]r.sub.6., r.sub.7., r.sub.8.[right brace], [left brace]r.sub.2., r.sub.3.[right brace] are some of the nontrivial subregions. We use both r; and j interchangeably to denote a basic region.

The motivation for selecting the four operations [left brace]h, v, s, S[right brace] and defining the subclass of T*-plans are: The simplicity of these operations, their ability to generate a sufficiently large and interesting class of dissections, and given a dissection D, one can detect with some reasonable computation effort the presence of these partitioning operations in D. The proofs of various lemmas and theorems in this section basically demonstrates the last point. The consideration of T*-plans also suffices to illustrate the basic properties of the subregion representation and the types of analysis possible for a family of dissections that is generated by a fixed set of partitioning operations [12, 13].

2.1 The Subregion Tree t(D) of a T*-plan

We can represent a T*-plan D as an ordered tree t(D) that shows the nested structure of its subregions. Formally t(D) is defined as follows. The terminal nodes of t(D) are labeled in a one-to-one fashion by the basic regions of D. Each intermediate node x in t(D) corresponds to a subregion of D and is labeled with one of the letters [left brace]h, v, s, S[right brace] that describes the type of partitioning operation applied to that subregion. The tree t(D) is called the subregion (tree) representation of D. Figure 3(a) shows the subregion representation of the T*plan in Figure 1(a). An alternative view of the T*-plan, show in Figure 3(b), depicts the actual dissection for each intermediate node in terms of its child nodes. The close correspondence between these two views of a T*-plan is a consequence of Lemma 1. A node of t(D) with the label x = h, v, s, or S is referred to as an x-node. In particular, a node with the label s or S is called a spiral node. We assume here that the tree t(D) is normalized in the sense that if x is the parent of a node y, then x and y do not have the same label h or v. A child of a spiral node may, however, be a spiral node with the same or different (s or S) label. To normalize a tree t(D), we successively merge a child node and its parent node into a single node if they have the same h or v label, until here are no such parent-child node pairs. The advantages of the normalization of t(De are that it reduces the number of intermediate nodes in the tree and makes the tree unique (see Figure 4(a)-(b)). An alternative way to normalize t(D) would be to convert it to a right-biased binary tree; the tree on the left side of Figure 4(c) is such a tree. A small advantage of this binary form is that the intemediate nodes of the binary form of t(D) are in direct one-to-one correspondence with the walls of D. A similar correspondence, though in a somewhat different form, holds also for the normalized form chosen here (see Theorem 1).

LEMMA 1. Let D be a T*-plan and t(D) its associated subregion tree. Then the nodes of t(D) are in one-to-one correspondence with the subregions of D, excluding those subregions that are formed by the union of two or more subregions corresponding to the consecutive child nodes of an h-node or a v-node of t(D).

PROOF. Each intermediate node x in t(D) corresponds to the subregion consisting of the basic regions that are at the terminal nodes of the subtree at x. With the exceptions as stated in Lemma 1, we show that these are the only subregions of D. If D is a basic region or is obtained by a single application of the operations h, v, s, and S, then there is nothing to prove. The general case is proved by induction on the number of partitioning operations in D. First we note that, if the root of t(D) is an s-node, then since each junction in D i a T-junction each subregion is either one of the five D.sub.j.s corresponding to the five children of the root of t(De or is contained in one of them. If the root of t(D) is an h-node or a v-node, then each subregion that is not properly contained in, or equal to, one of the D.sub.j.s associated with the children of the root, must be equal to the union of two or more D.sub.j.s which correspond to the consecutive child nodes of the root. Thus the lemma is true for subregions that are not properly contained within any of the D.sub.j.s. If the subregion is contained in one of the D.sub.j.s, then the lemma is true by the induction hypothesis.

Lemma 1 shows that, with a few obvious exceptions, the subregions of a T*-plan basically correspond to the intermediate nodes of t(D). If t.sub.j. is the subtree of t(D) at a node x, we denote by D(t.sub.j.) both the subregion associated with the node x and its dissection corresponding to the tree t.sub.j.

2.2 The Wall Representation w(D)

An horizontal wall (in short, an h-wall) in a T-plan is defined to be a maximal horizontal line segment [6]. A vertical wall (in short, a v-wall) is defined similarly. The wall representation w(D) of a T-plan consists of all the walls in D, where each wall is written as an ordered pair of lists of the basic regions adjacent to the wall. An h-wall w is written as w = (N(w), S(w)) where N(w) = the list of basic regions bordering with the wall w from above (north), and S(w) = the list of basic regions bordering with the wall w from below (south). Similarly a v-wall is written as w = (W(w), E(w)) where W(w) = the list of basic regions bordering with the wall w from left (west), and E(w) = the list of basic regions bordering with the wall w from right (east). We also denote a wall by w = (L.sub.1.(w), L.sub.2.(w)) or simply as w = (L.sub.1., L.sub.2.). The lists N(w) and S(w) of an h-wall are ordered from west-to-east, and the lists W(w) and E(w) of a v-wall are ordered from north-to-south. The lists W(w) and N(w) are also referred to as the first region lists and the lists E(w) and S(w) as the second region lists. Figure 5(a) shows the walls for the T-plan in Figure 1(a). The h-walls bordering with the external spaces N and S, and the v-walls bordering with W and E are called the external walls. They are referred to as the north-wall, south-wall, and so on. The other walls are called the internal walls. We remark that our definition of a wall does not include the [plus-or-minus] indicators used in [6] to distinguish the h-walls from the v-walls. In fact, we show in Lemma 3 that one can uniquely identify the h-walls and the v-walls of a t-plan D from its wall representation w(D). The following lemma is easily proved by induction using the property of T-junctions, and the proof is omitted here.

LEMMA 2. Let D be a T*-plan and let D.sub.j., 1 [is less than or =] j [is less than or =] k, be the subregions corresponding to the child nodes of the root of t(D). Then each internal wall of D is either an internal wall of one of the D.sub.j.s or corresponds to a dividing line of the partition corresponding to the root of t(D).

If the root of t(D) is an s-node or an S-node, then there are four dividing lines corresponding to the spiral partition for the root node. Two of these lines form internal h-walls and the other two form internal v-walls in D that are not contained in any of the D.sub.j.s. If the root node is an h-node with k children, then there are (k - 1) such internal h-walls in D; similarly, if the root node is a v-node, there are (k - 1) such internal v-walls. The first part of the equivalence between the wall representation and the subregion representation is given by the following theorem.

THEOREM 1. The subregion representation t(D) of a T*-plan uniquely determines its wall representation w(D).

PROOF (by induction). The theorem is trivially true if D consists of a single basic region, in which case the tree t(D) consists of only the root node. Assume now that D has n [is greater than or] 2 basic regions. In view of Lemma 2, we basically need to show how to construct the four external walls of D and those internal walls of D that correspond to the dividing lines of the partition due to the root node of t(D). We give the details for the case where the root node of t(D) is an h-node. The cases when the root of t(D) is a v-node, s-node, or S-node are similar.

Suppose now that the root node of t(D) is an h-node and has k childen. Table I(a) shows the equations for determining the external walls of D. Here, t.sub.1., t.sub.2.,..., t.sub.k are the subtrees of t(D) from left to right, and w.sup.N.(t.sub.j.) denotes the north wall of the dissection D(t.sub.j.), and so forth. For example, the sixth equation shows that the east side of the west wall of D is the concatenation (* = the concatenation operator) of the east sides of the west walls of D(t.sub.j.)s, taken in the order t.sub.1., t.sub.2., ..., t.sub.k. Table I(b) shows the equations for the (k - 1) internal h-walls of D corresponding to partitioning lines for the root of t(D). Here, w.sub.i.(t) denotes the ith such h-wall of D. The equations in Table I and the other similar equations for the cases where the root of t(d) is v-node, s-node, or S-node can be used recursively to construct the h-walls for a T*-plan starting with the equations N(w.sup.S.(j)) = S(w.sup.N.(j)) = E(w.sup.W.(j)) = W(w.sup.E(j)) = j for the basic region r.sub.j., 1 [is less than or =] j [is less than or =] n.

2.3 The Equivalence os w(D) and t(D) for a T*-plan

We now proceed to establish the other half of the equivalence between t(D) and w(D) for the T*-plans, (i.e., show that the wall w(D) uniquely determines the tree t(D)). The proof of this fact depends on several lemmas, some of which are fairly straightforward. We state Lemma 3 and the algorithm A.sub.1. for the general case of T-plans although we will use them subsequently only for the T*-plans.

LEMMA 3. Given the wall of representation w(D) of a T-plan D, one can uniquely identify the h-walls and the v-walls of D in w(D). In particular, one can find the h-walls that extend from W to E and the v-walls that extend fron N to S.

PROOF. The external walls w = (l.sub.1., L.sub.2.) of D are easily identified by the fact that one of L.sub.1. and L.sub.2 must equal the list (N), (S), (W), or (E). The classification of the external walls into h-walls and v-walls is also trivial. The identification of the remaining v-walls proceeds by first identifying the successive vertical layers V.sub.j. (to be defined shortly) of the basic regions of D. All other walls that are not identified as v-walls then give the h-walls of D. For the purpose of computational efficiency in algorithm A.sub.1. below, however, we will identify the h-walls in parallel with the v-walls, namely, by finding those h-walls that extend to the west as far as V.sub.j. but not to V.sub.j-1. The first vertical layer V.sub.1. consists of the basic regions that border the external region W (i.e., V.sub.1. is the second region list of the west v-wall). For j > 1, we define V.sub.j. to be the set of all basic regions r.sub.i. that has the property that each region r.sub.k. that has a common vertical boundary with the west side of r.sub.i. is in V.sub.j-1. In terms of the walls in w(D), this is equivalent to saying that there is a wall w = (L.sub.1.(w), L.sub.2.(w)) such that L.sub.1.(w) V.sub.j-1., L.sub.2.(w) V.sub.j-1. = [phi], and r.sub.i. L.sub.2.(w). The wall w is necessarily a v-wall. If we regard each V.sub.j. as an ordered list, then v.sub.j. is obtained by replacing the sublist L.sub.1.(w) V.sub.j-1. by the list L.sub.2.(w) for each such wall w. Here, L.sub.1.(w) consists of one or more consecutive items of V.sub.j-1. Note that the condition L.sub.1.(w) v.sub.j-1. by itself may not be sufficient to determine that w is a v-wall; for example, consider the case when both L.sub.1.(w) and L.sub.2.(w) consists of a single basic region belonging to v.sub.j-1. We can identify the h-walls w' = (L.sub.1.(w'), L.sub.2.(w')) that extend to the left as far as to the layer v.sub.j. but not to v.sub.j-1. by the criteria that the first basic region in both the lists L.sub.1.(w') and L.sub.2.(w') belong to V.sub.j.

Finally, an internal h-wall w = (L.sub.1., L.sub.2. extends from W to E if the first member in both L.sub.1. and L.sub.2. belongs to the second list of the west wall and the last member in both L.sub.1. and L.sub.2. belong to the first list of the east wall. Similarly, for the v-walls. This proves the lemma.

The proof of Lemma 3 gives the following algorithm A.sub.1. for identifying the h-walls and the v-walls in w(D). Here, for computational efficiency, we replace the test "the first member of both L.sub.1.(w) and L.sub.2.(w) belong to V.sub.j." for an h-wall by the equivalent condition "L.sub.2.(w) V.sub.j. [is not =][phi]" (that is also equivalent to "the first member of L.sub.2.(w) belongs to V.sub.j."), when applied to the walls that are not classified yet. Also, we perform this test first since it is computationally easier than testing for "L.sub.1.(w) V.sub.j. and ..." in identifying a v-wall bordering with V.sub.j. Once the h-walls that extend to the west up to V.sub.j. have been identified, it suffices to test only the first part "L.sub.1.(w) v.sub.j." for the v-walls. Since verifying "L.sub.1.(w) v.sub.j." would require testing it many times for each v-wall w until it gets classified, we use the following data structures to implement it. We let B.sub.1. to be the array whose ith item B.sub.i.[i] is a list of pointers to the internal walls w = (L.sub.1.(w), L.sub.2.(w)) in w(D) such that R.sub.i. L.sub.1.(w). We also use the array C, where C[w] is initially equal to the number of items in L.sub.1.(w . The list V.sub.j. is processed by reducing the count C[w] by one for each r.sub.i. V.sub.j. and w pointed by a pointer in the list B.sub.1.[i]. Thus L.sub.1.(w) v.sub.j. if and only if C[w] becomes 0 on processing of V.sub.j. Note that in this implementation the ordering of the items in V.sub.j.or the lists L.sub.1.(w) are not relevant. To perform the tests "L.sub.2.(w) v.sub.j.", we use the array B.sub.2. whose ith item is a list of pointers to the internal walls w = (L.sub.1.(w), L.sub.2.(w)) such that r.sub.i. L.sub.2.(w). (If we want to make use of the ordering of the basic regions in L.sub.2.(w), it would have sufficed to define B.sub.2.[i] to be the list of pointers to the walls w such that r.sub.i. is the first member of L.sub.2.(w).) The construction of the arrays B.sub.1., B.sub.2., and C requires a simple linear scan of each L.sub.1.(w) and L.sub.2.(w) for the internal walls w w(D), and thus needs O(n) time since each basic region belongs to at most four of the lists L.sub.1.(w) and L.sub.2.(w). (See [1] for the list implementations.)

Algorithm A.sub.1. Identification of h-walls and v-walls in w(D).

Input: [omega] = set of all walls in a T-plan, where each wall is given in the form w = (L.sub.1.(w), L.sub.2.(w)). (The north-to-south or the west-to-east ordering of the lists L.sub.1. and L.sub.2. are not used.)

Output: The identification of h-walls and v-walls, and determination of the h-walls that extend from W to E and the v-walls that extend from N to S.

(1) [Find the external walls.] Find the walls W.sub.1., w.sub.2., w.sub.3., and W.sub.4. such that L.sub.1.(w.sub.1.) = (N), L.sub.2.(w.sub.2.) = (S), L.sub.1.(w.sub.3.) = (W), and L.sub.2.(w.sub.4.) = (E). The north h-wall is w.sub.1., the south h-wall is w.sub.2., the west v-wall is w.sub.3., and the east v-wall is w.sub.4.

(2) [Process the internal walls.] Construct the arrays B.sub.1., B.sub.2., and C from the remaining walls in w(D) as defined in the discussion following Lemma 3.

(3) Let V = L.sub.2.(w.sub.3.).

(4) [Find the h-walls that extend to west up to V and the v-walls that border with V.] Do the following:

(a) Let L = concatenation of the lists B.sub.2.[i] for r.sub.i. V, taken in some order. For each wall w L (i.e., pointed from L), if w is not yet classified, then classify it as an h-wall.

(b) Let L = concatenation of the lists B.sub.1.[i' for r.sub.i. V, taken in some order. For each occurence of w in L (i.e., pointed from L), if w is unclassified then reduce C[w] by one, and classify it as a v-wall in case C[w] becomes 0.

(5) [Form new V.] For the v-walls w = (L.sub.1., L.sub.2. identified in step 4(b), let V = concatenation of the L.sub.2.s in some order. If there is only one v-wall w found in step 4(b), then w extends from N to S.

(6) Repeat steps (4)-(5) until V = (E).

(7) Determine the h-walls extending to W and E as in the proof of Lemma 3.

THEOREM 2. Algorithm A.sub.1. correctly identifies the v-walls and the h-walls of a T-plan D, and determines those h-walls that extend from W to E and the v-walls that extend from N to S. It takes O(n) time, where n is number of basic regions in D.

PROOF. The correctness of A.sub.1. follows from the proof of Lemma 3 and the remarks following it. The steps (1)-(2) take O(n) time. The lists V in the successive iterations of step (4) being disjoint, the total computation time for steps (4)-(5) is also O(n). Step (7) can be implemented easily in O(n) time. Thus the total time is O(n).

We need the following definitions from [5] for computing the subregion bounded by a given set of walls. We say l(r.sub.i., r.sub.j.)--to be read as "r.sub.i. to the left of r.sub.4."--if there is a v-wall w = (L.sub.1., L.sub.2.) such that r.sub.i. L.sub.1 and r.sub.j. L.sub.2. We write l(i, j) in short for l(r.sub.i., r.sub.j). The set of basic regions R.sub.i.(w) to the left of a v-wall w = (L.sub.1., L.sub.2.) is given by R.sub.l.(w) = [left brace]r.sub.i.:r.sub.i. L.sub.1. or there is a chain (i, i.sub.1., i.sub.2., ...,i.sub.k., j), k [is greater than or =] 1, such that l(i, i.sub.1.), l(i.sub.1., i.sub.2.), ..., l(i.sub.k., j), and r.sub.j. L.sub.1.[right brace].

Similarly, we have the relation a(r.sub.i., r.sub.j.)--to be read as "r.sub.i. above r.sub.j."--if there is an h-wall w = (L.sub.1., L.sub.2.) such that r.sub.i. L.sub.1. and r.sub.j. L.sub.2. We write a(i, J) in short for a(r.sub.i., r.sub.j.). The set of basic regions r.sub.a.(w) above an h-wall w = (L.sub.1., L.sub.2.) is then given by R.sub.a.(w) = [left brace]r.sub.i.:r.sub.i. L.sub.1. or there is a chain (i, i.sub.1., i.sub.2., ..., i.sub.k. j), k [is greater than or =] 1, such that a(i, i.sub.1.), a(i.sub.1., i.sub.2.), ..., a(i.sub.k., j), and R.sub.j. L.sub.2.[right brace].

In view of Lemma 3, the wall representation w(D) completely determines the relations l(i, j) and a(i, 4), and therefore the sets R.sub.l.(w) and R.sub.a.(w). We say r.sub.i. is below r.sub.j. if r.sub.j. is above r.sub.i.; similarly, r.sub.i. is to the right of r.sub.j. if r.sub.j. is to the left of r.sub.i. We write R.sub.b.(w) for the set of basic regions below an h-wall w, and R.sub.r.(w) for the set of basic regions to the right of a v-wall w.

We make one more definition. We define the north-to-south ordering among the h-walls that extend to the west up to W in terms of the wall structures as follows. Let ((W), (r.sub.1., r.sub.2., ..., r.sub.k.)) be the external west wall. If w and w' are two h-walls that extend to W, then we write w < w' if i < j, where r.sub.i. and r.sub.j. are the first member of the first region lists of w and w', respectively.

The north-to-south ordering of the h-walls extending to E is defined similarly. In particular, for the h-walls that extend from W to E, the two orderings defined by the external west wall and the external east wall are one and the same. The left-to-right ordering of the v-walls, extending to N and that for the v-walls extending to S are defined similarly and is denoted by the same symbol "<"; moreover, for the v-walls that extend from N to S, the two orderings are also one and the same.

LEMMA 4. Given the wall representation W(D) of a T*-plan D, one can determine whether the root node of t(D) is an h-node or a v-node, and in that case one can determine the subregions corresponding to each child of the root. It takes O(n) time to make these determinations.

PROOF. The successive v-walls determined in step (5) of algorithm A.sub.1., if any, are the internal v-walls in the left-to-right order that extend from N to S. If at least one such v-wall is found, then the root node of t(D) is a v-node. The set of all basic regions in the list V (steps (3) and (5)) between the identification of two such successive v-walls w.sub.1. and w.sub.2. give the subregion bounded by these two v-walls, namely, [left brace]r.sub.i.:r.sub.i. R.sub.l.(w.sub.2.) - R.sub.l.(w.sub.1.)[right brace]. These are the regions corresponding to the children of the root of t(D) in the left to right order. (For the first child node, take w.sub.1. to be the external west wall.)

If there exists an internal h-wall extending from W to E, then the root node of t(D) is an h-node. The simplest way to determine the subregions corresponding to the children of the root node is to apply a slightly modified form of the algorithm A.sub.1. where the method of identifying the h-walls and the v-walls are reversed, namely, by letting V correspond to a horizontal layer of basic regions, and so on. Initially, V would be the second region list of the external north wall. This proves the lemma.

LEMMA 5. If D is a T-plan and R' is a subregion of D, then w(D) uniquely determines the wall representation w(R') of R'.

PROOF. For each wall w = <L.sub.1.(w), L.sup.2.(w)> in D, we form W' = [L.sub.1.(w'), L.sub.2.(w')], where L.sub.1.(w') * R', j = 1, 2. Here, L.sub.1(w) * R' is a sublist of one or more consecutive elements of the basic regions of R'. If both L.sub.1.(w') and L.sub.2.(w') are empty, then we throw away w'. On the other hand, if w is an h-wall in D and only L.sub.1.(w') = [phi], then we redefine L.sub.1.(w') to be (N); similarly, if only L.sub.2.(w') = [phi], then we redefine it to be (S). We have similar rules for redefining L.sub.1.(w') to be (W) and L.sub.2.(w') to be (E) when w is a v-wall. The set of all walls w' obtained in this way gives the wall representation of R'. *

Note that if the root node of t(D) is a v-node and w is a v-wall identified in step (5), then the set of h-walls and v-walls identified in step (4) since the previous v-wall w'(w' = w.sub.3., if w is the first v-wall obtained by step (5)) identified by step (5) equals the internal walls of the subregion bounded by the v-walls w' and w extending from N to S. The external walls of this subregion are easily constructed from the walls w and w' and the external north and the south walls. Similarly for the case where the root node of t(D) is an h-node and we use the modified form of A.sub.1 as mentioned in the proof of Lemma 4. Thus the construction given in the proof of Lemma 5 will need to be used only for the case where the root node of t(D) is a spiral node.

LEMMA 6. If D is a T*-plan where the root node of t(D) is a spiral node, then the wall representation w(D) uniquely determines the subregions D.sub.j., 1 [is less than or =] j [is less than or =] 5, corresdponding to the five children of the root node. One can also determine whether the root node t(D) is an s-node or an S-node.

PROOF. The root node of t(D) is a spiral node if it is not an h-node or a v-node. We first show that the four corner subregions D.sub.j., j [is not =] 3, of the spiral partition for the root node are uniquely determined. The subregion D.sub.3 is then given by the remaining basic regions that do not belong to any of the corner subregions. the following is a unique characterization of the subregion D.sub.1.; a similar characterization exists for each of D.sub.2., D.sub.4., and D.sub.5. The subregion D.sub.1 is the one that is bounded by the north wall, the west wall, and two other internal walls w.sub.1 and w.sub.2., where

(1) w.sub.1 is the southmost h-wall that extends to W and that meets a v-wall extending to N, and

(2) w.sub.2 is the eastmost v-wall that extends to N and that meets an h-wall extending to W.

The criteria (1) is based on the fact that any h-wall that extends to W and is not part of D.sub.1 is contained in D.sub.2 and therefore cannot meet a v-wall extending to N. The criteria (2) is obtained similarly. To complete the proof of the lemma,' it remains to formally define the term "meet" directly in terms of the walls w(D). We have an h-wall w.sub.1 meets a v-wall w.sub.2 if the last (resp., the first) members of both the region lists of w.sub.1 belongs to the first (resp., the second) region lists of w.sub.2., or a similar condition holds with the role of w.sub.1 and w.sub.2 reversed.

Finally, having identified the walls w.sub.1 and w.sub.2 that satisfy the criteria (1)-(2), we have the root node of t(D) is an s-node if and only if the last member in the first region list of w.sub.1 belongs to the first region list of w.sub.2.; otherwise, the root node is an S-node. (See Figure 2(c)-(d).) The set of basic regions in D.sub.1 then equals R.sub.a (w.sub.1.) or R.sub.1.(w.sub.2.) according as the root node of t(D) is an s-node or an S-node, respectively. The lemma is proved. *

Algorithm A.sub.2.: Determination of the spiral label s or S for the root node of t(D) and the subregions D.sub.1., D.sub.2., ..., D.sub.5 for its child nodes.

Input: The wall representation w(D) of a T*-plan D, where the root node of t(D) is a spiral node.

Output: The label (s or S) for the root node of t(D) and the subregions D.sub.1., D.sub.2., D.sub.3., D.sub.4., and D.sub.5 created by the spiral operation for the root node.

(1) Group the internal walls in w(D) that extend to one of the boundaries N, S, W, and E as follows. H.sup.W = the internal h-walls that extend to W, H.sup.E = internal h-walls that extend to E, V.sup.N = the internal v-walls that extend to N, and V.sup.S = the internal v-walls that extend to S.

(2) Order the walls in H.sup.W and H.sup.E from north to south, and the walls in V.sup.N and V.sup.S from west to east using the ordering "<".

(3) Find the walls w.sub.1., w.sub.2., W.sub.3., and w.sub.4 with the following properties (see the proof of Lemma 6 for the definition of "meet"). w.sub.1 = the southmost wall in H.sup.W that meets a v-wall in V.sup.N., w.sub.2 = the eastmost wall in V.sup.N that meets w.sub.1., w.sub.3 = the southmost wall in H.sup.E that meets w.sub.2., and w.sub.4 = the westmost wall in V.sup.S that meets w.sub.3.

(4) If the last item of the first region list of w.sub.1 belongs to the first region list of w.sub.2., then the root of t(D) is an s-node; otherwise, it is an S-node.

(5) Define the subregions D.sub.j., 1 [is less than or =] j [is less than or =] 5, as follows according as the root of t(D) is an s-node or an S-node. Root = s-node Root = S-node Subregions Subregions D.sub.1 = R.sub.a.(w.sub.1.) D.sub.1 = R.sub.1.(w.sub.2.) D.sub.2 = R.sub.1.(W.sub.4.) D.sub.2 = R.sub.b.(w.sub.1.) D.sub.4 = R.sub.r.(w.sub.2.) D.sub.4 = R.sub.a.(W.sub.3.) D.sub.5 = R.sub.b.(w.sub.3.) D.sub.5 = R.sub.r.(w.sub.4.) D.sub.3 = the basic regions in D which are not in D.sub.1 * D.sub.2 * D.sub.4 * D.sub.5.

THEOREM 3. Algorithm A.sub.2 takes O(n) time, where n is the number of basic regions in the T*-plan D.

PROOF. The steps (1)-(2) require scanning the external walls and the first and the last members of the two lists L.sub.1 and L.sub.2 in the internal walls w = [L.sub.1., L.sub.2.] in w(D). Thus they can be implemented in O(n) time (using appropriate lists of pointers similar to the arrays B.sub.1 and B.sub.2 in algorithm A.sub.1.). Similarly, step (3) requires O(n) time. Step (4) takes a constant time, and finally step (5) requires scanning of the various walls only once, and can be implemented in O(n) time (again using arrays similar to B.sub.1 and B.sub.2 in algorithm A.sub.1.). *

We are now in a position to prove the final theorem.

THEOREM 4. If D.sub.1 and D.sub.2 are two T*-plans, then they have the same subregion representation t(D.sub.1.) = t(D.sub.2.) if and only if they have the same wall-representation.

PROOF. Theoren 1 shows the only if part. We prove the if part by showing that for a T*-plan D, its wall representation uniquely determines the tree t(D). The proof is by induction on the number of basic regions in D. If D consists of only one basic region, then there is nothing to prove. Assume that the theorem is true for all T*-plans of order [is less than or =] n, and that D has order (n + 1). First, in view of Lemmas 4 and 6, we have the label (h, v, s, S) of the root node of t(D) is uniquely determined and so are the subregions corresponding to the children of the root. Since each of these subregions is a T*-plan of order [is less than or =] n, and the walls of the subregions can be obtained from those of D, by Lemma 5, the theorem is proved. *

The complete algorithm for determination of t(D) from w(D) is given below, where we makeuse of the algorithms A.sub.1 and A.sub.2.

Algorithm A.sub.3.: Determination of t(D) from w(D). Input: The wall representation w(D) of a T*-plan. Output: The subregion tree representation t(D).

(1) If there is only one basic region, then t(D) consists of a single node with that label.

(2) Use algorithm A.sub.1 and Lemma 4 to determine if the label of the root of t(D) is h or v. In that case, also determine the walls w(D.sub.j.), 1 [is less than or =] j [is less than or =] k, for the subregions D.sub.1., D.sub.2., ..., D.sub.k corresponding to the children of the root node as in the proof of Lemma 4. Go to step 4.

(3) Apply algorithm A.sub.2 to determine whether the root of t(D) is an s-node or an S-node, and the associated subregions D.sub.j., 1 [is less than or =] j [is less than or =] 5. Determine the wall representations w(D.sub.j.) for each subregion D.sub.j by Lemma 5 and the remarks following it.

(4) Apply the algorithm recursively to each D.sub.j and determine the tree t(D.sub.j.) from w(D.sub.j.).

(5) Let t(D.sub.1.), t(D.sub.2.), ..., be the subtrees of the root of t(D), in that order.

THEOREM 5. The subregion representation t(D) of a T*-plan can be obtained from its wall representation w(D) in time O(n.sup.2.), where n is the number of basic regions in D.

PROOF. By Theorems 2 and 3, the steps (2)-(3) take O(n) time, including the construction of the walls w(D.sub.j.) for each of the subregions D.sub.j. By the same argument, the construction of each layer of the tree t(D), that is, the [h, v, s, S] labels of all nodes which are at a distance d [is greater than or =] 1 from the root node and the subregions and walls for the children of those nodes, requires O(n) time. Thus the total time is at most O(n.sup.2.), or more precisely, O(h.n) where h is the height of the tree t(D). *

3. SOME COMMENTS ON THE ABSTRATION

t(D)

We briefly comment here on the use of t(D) as an abstraction scheme for a T*-plan. Although the wall representation of a T*-plan is theoretically equivalent to its subregioni representation, the latter has the important advantage that it gives rise to a series of "natural" abstractions. Abstractions are important as a means for generating a dissection by the method of successive refinements, which is also called hierarchical placement [10]. Initially, one forms a decomposition of the set of basic regions into groups, and determines the possible placements of these groups as a whole within the design space R. As the refinement process progresses, each group is broken down into smaller subgroups and the positioning of these subgroups are determined within the space occupied by that group, and so on. The process stops when each group consists of a single basic region and the layout of the dissection is completely determined. Abstractions are also important for classifying a set of dissections. For example, we can classify the T*-plans by their subregion representatins, that is by considering two T*-plans D.sub.1 and D.sub.2 to be in the same class if t(D.sub.1.) = t(D.sub.2.). Other higher level, and thus less-refined, classifications can be based on specific properties of the trees t(D). For example, the height of t(D) (i.e., the maximum length of a path from the root of t(D) to a terminal node), the number of s-nodes and S-nodes in t(D), and so on. Yet other classifications can be obtained by first taking some transformation of the tree t(D) and then defining the various classes based on the transformed t(D)s. We describe below two such transformations. These abstraction operations may be applied repeatedly to derive other higher level abstractions. Note that each basic region in an abstraction is either a subregion or a basic region of the original T*-plan.

(1) Type-1 abstraction (pruning): Replace the subtree at an intermediate node x in the tree t(D) by a single node and remove its exiting [h, v, s, S] label. An abstraction of this type hides the details of the dissection for the subregion at x by regarding it as a "fat" basic region.

(2) Type-2 abstraction (merging): Let x be an h-node or a v-node in t(D) with k [is greater than or =] 3 children and let y.sub.1 and y.sub.2 be two consecutive terminal child nodes of x. Then merge y.sub.1 and y.sub.2 into a single node z, reducing the number of children of x to (k - 1). The subregion associated with node z is the union of those for y.sub.1 and y.sub.2.

Note that the Type-1 abstraction can be used at any intermediate node of t(D). In some cases, a Type-1 abstraction is the same as the result of multiple applications of Type-2 abstractions extended to the case of k = 2. Figure 6(a) shows the tree resulting from the tree in Figure 3(a) by first creating a Type-1 abstraction with the "fat" basic regions [left brace]1, 2, 3[right brace], [left brace]4, 5[right brace], and [left brace]6, 7, 8[right brace], and then by creating a Type-2 abstraction giving the "fat" basic region [left brace]6, 7, 8, 9[right brace]; Figure 6(b) shows a T*-plan corresponding to this tree (cf. the T*-plan in Figure 1(a)). The choice of the node X in the abstraction operations (1)-(2) may be based on various properties of x such as the total number of basic regions contained in the subregions represented by x. Other useful properties may be the dimensions (length and width) or areas of the subregion X or those of the basic regions contained in X, or the distance of X from the root of t(D), or the height of the subtree at X, and so forth. For the case of distance, one may convert all non-terminal nodes at a distance m from the root of t(D) to a terminal node by the repeated application of pruning operation. For the case of heights, all nodes at which the subtree is of height m may be converted to a terminal node. Figure 7(a)-(b) show the results of these transformations for m = 2 on the tree representation t(D) in Figure 3(a).

4. CONCLUSION

If we view the four partitioning operations [left brace]h, v, s, S[right brace] of a T*-plan as the transformations rules of a shape grammar [18], then the T*-plans are simply the set of dissections generated by that grammar. We believe that the equivalence theorem between the wall representation and the subregion representation can be generalized to other classes of T-plans for which there is a suitable regular, or more generally, a context-free like shape grammar. The subregion representation tree t(D) for such a dissection corresponds to the parse tree of D in the terminology of formal grammars. Moreover, we believe that it would be possible to find efficient algorithms, that is, of order O(n.sup.k.) for some small constant k depending on the complexity of the basic partitioning operating in the grammar, for the conversion between the two representation schemes for these classes of dissections. As we noted earlier, there are many interest T-plans that are not T*-plans. In particular, it is not difficult to see that there is an infinite hierarchy of spirals S.sub.1., S.sub.2.,..., such that no S.sub.i can be generated from [left brace]S.sub.j.; j < i[right brace], even in combination with h- and v- operations.

As for the use of t(D) as an abstraction scheme, we believe that the notion of subregion closely resembles the way an architect visualizes a design space. From the consumer's point of view, a dissection that represents a residential floor-plan may be perceived in many ways as "clusters" (and clusters of clusters and so on) of the basic regions, and not just as a collection of walls. Thus an abstraction mechanism based on clusters might be more effective in relating certain aspects of the user's perception and the generation of the corresponding designs constraints than that based on the wall representation. The subregions in a T*-plan are a specialized form of clusters, namely, that have a rectangular boundary. A general theory that includes non-rectangular subregions as an abstraction unit (cluster) seems a difficult task. For the T*-plans, we could perhaps allow merging of the spaces D.sub.2 and D.sub.1 (or D.sub.2 and D.sub.3., etc.) created by a spiral operation to accomodate non-rectangular subspaces. More generally, one may allow merging two subregions if they share a portion of their boundary. In any case, some control must be exercised in such merging operation or else the subspaces of the abstraction will soon cease to have any meaning. In [5], methods have been given for handling the case where the total design space R of a dissection is not a rectangle.

Acknowledgments. We would like to express our appreciation to the anonymous referees whose comments have been helpful in strengthening the paper.
COPYRIGHT 1988 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.