2.1. Definition

The underlying schema (Hasse diagram) in Figure 1 is typical of hierarchical decompositions of shapes and its inspection may reveal their structure.

We notice that the hierarchy contains the least upper bound for every pair of its elements, but lacks the greatest lower bound. This renders hierarchical decompositions join-semilattices with a greatest element, which is the shape analyzed by the hierarchy.

Each element of the hierarchy, with the exception of its atoms, covers at least two elements, which renders such elements join-reducible. In contrast, each element, with the exception of the greatest element, is covered by exactly one element, which means that only comparable elements have meets.

For every nonempty part of the coffee table in Figure 1 there is an element in the hierarchy that uniquely represents it. This element is the least upper bound of the part. For example, in Figure 2 shape (a) is a part of the coffee table while shape (b) is its least upper bound with respect to the hierarchy in Figure 1.

Fig. 2.

(a) A part of an IKEA coffee table and (b) its representation in the hierarchy.

Although nonempty parts are uniquely represented, the hierarchy does not satisfy the unique representation requirement. It lacks a unique element to top the empty shape, which is part of every shape. Every atom of the hierarchy is as good of a representation of the empty shape as any other atom. This may be rectified by including the empty shape in the hierarchy. Now the empty shape represents itself and the hierarchy satisfies the unique representation requirement.

The inclusion of the empty shape has some interesting consequences on the structure of the hierarchy. Now every pair of noncomparable elements in the hierarchy has a meet that is the empty shape. Pairs of comparable elements already have meets, as noted earlier, so that the hierarchy is closed under the meet operation. The structure of the hierarchy changes from a semilattice to a lattice. This rather unusual representation (hierarchies are usually considered trees or join-semilattices) offers several advantages:

1. 1. Because hierarchies contain the shape they analyze and (now) the empty shape they are bounded decompositions. The latter are known to behave like shapes and form an algebra isomorphic with an appropriate shape algebra (Krstic, Reference Krstic and Gero2004, Reference Krstic2005).

2. 2. Hierarchies (now) have the unique representative for the empty shape and may satisfy the unique representation requirement to qualify as shape approximations.

3. 3. Hierarchies are (now) lattices and so are topologies, which we will show later, so that a unique characterization of both is possible.

We now give a formal definition of a hierarchy.

The meet-irreducibility condition assures that no nonempty element of a hierarchy is a part of two disjoint components of the design. As a consequence, between any two (comparable) components of the design there is a unique path, traversing nonempty elements of the hierarchy, which means that the design is assembled in a unique way. In contrast, the join-reducibility condition is necessary to make sure that proper parts of any component of the design when assembled constitute precisely that component. This condition also prevents chains from being mistaken for hierarchies.

Note that inclusion of 0 is formal in nature and we omit 0 in diagrams in order to maintain the familiar look of hierarchies. We also omit 0 in element counts.

2.2. Properties of hierarchical decompositions of shapes

Hierarchies are rich in properties, but we will only examine those that are relevant to design. Prime among such properties is the ability to satisfy the unique representation requirement, which qualifies hierarchies as shape approximations.

We observed that the hierarchy in Figure 1 satisfies the requirement, but not all hierarchies have this property. Many hierarchies that serve to order descriptions or properties of designs do not have unique representations for design parts.

For example, a hierarchy in Figure 3 describes a small house consisting of a kitchen, living room, hallway, bedroom, bathroom, walk-in closet, stairway, and garage. In this hierarchy of names, which distinguish spaces, elements combine disjunctively without a conjunctive possibility. The bedroom has no common part with the bathroom or walk-in closet, although together they are the private spaces of the house. The same is true for the living room, hallway, kitchen, stairway, and garage, which are the public spaces. If we replace the names with the shapes they represent, the conjunction of elements become possible, but the hierarchy is oblivious to that.

Fig. 3.

The hierarchy of spaces for a small house.

For example, the hierarchy in Figure 3 may represent the Ohlenbusch residence in San Antonio, Texas, designed by Darryl Ohlenbusch Design and completed in 1995 (Ojeda, Reference Ojeda1997, p. 128). Its plan in Figure 4a appears as a top element of the hierarchy, and spaces d–k representing the stairway, garage, kitchen, bathroom, living room, bedroom, closet, and hallway, respectively, are the atoms of the hierarchy. Disjunctive combinations of atoms form the public space of the house as well as its private space (Fig. 4b and 4c, respectively). This enumerates all of the elements of the hierarchy as prescribed by the schema (Hasse diagram) in Figure 3. What is not prescribed by the schema is the possibility for conjunctive combinations. The kitchen and living room may combine (conjunctively) to reveal the walls they share. The same is true for other adjacent spaces like the kitchen and bathroom or the bathroom and bedroom. For example, the shape in Figure 5c is the wall between the kitchen (b) and bathroom (a). It is topped by these two shapes and also by some other elements of the hierarchy that include the two as parts. Because the kitchen and bathroom are noncomparable shapes, the shape in Figure 5c has two representatives, which violates the unique representation requirement.

Fig. 4.

The Ohlenbusch residence: (a) plan, (b) public space, (c) private space, (d) stairway, (e) garage, (f) kitchen, (g) bathroom, (h) living room, (i) bedroom, (j) closet, and (k) hallway.

Fig. 5.

The Ohlenbusch residence: (a) bathroom, (b) kitchen, and (c) a partitioning wall between the two.

Only hierarchies of certain structure satisfy the requirement in accordance with the following result.

Let a be a shape defined in U_ij, x its part, and X(a) a hierarchical decomposition of a. If X(a) satisfies the unique representation requirement then there is a shape y ∈ X(a) which represents x so that either x ≤ y or y ≤ x. Because X(a) − {0} is a join-semilattice, the former inequality holds and because y represents x uniquely, y is the least upper bound of x in X(a). Consequently, X(a) has the least upper bound for every part of a, which requires for X(a) to be closed under the product from U_ij. The product is, therefore, the meet operation of X(a). In contrast, if the meet from X(a) is the product from U_ij then X(a) is closed under the product, which defines a closure Γ on the set Β(a) of all parts of a such that Γ(Β(a)) = X(a). Part x is uniquely represented by its closure Γ(x), which is an element of X(a) so that X(a) satisfies the unique representation requirement.

Note that Γ is not a topological closure. Take, for example, a four-element hierarchy satisfying Proposition 1 and consisting of three atoms x, y, and z and their sum a. The sum of closures Γ(x) + Γ(y) = x + y, is different from the closure of the sum Γ(x + y) = a = x + y + z so that Γ is not a topological closure.

Hierarchies that satisfy Proposition 1 have atoms that are pairwise discrete. This is a corollary of Proposition 1: if x and y are atoms then x ∧ y = x · y = 0, hence, they are discrete. The set of atoms of such a hierarchy is a discrete decomposition of the shape analyzed by the hierarchy. This motivates the following definition.

We may now reformulate Proposition 1.

Meet operation of a discrete hierarchy is uniquely determined by the shapes that are its arguments. It equals their product, which remains the same regardless of the hierarchy the shapes belong to. This is not the case with the join operation. The latter is the least upper bound determined by its arguments, but also by all other elements of the hierarchy. For a discrete hierarchy X(a) with elements x and y meet is given by x ∧ y = x · y and join by x ∨ y = Γ(x + y), where Γ is a closure operator on Β(a) such that Γ(Β(a)) = X(a). A discrete hierarchy is defined by its join. We can have a kit of parts from which we assemble an object and we can do it in many different ways. Each of the ways defines a discrete hierarchy with a different join operation. The sizes of such hierarchies range from k + 1 to 2k – 1, where k is the number of parts in the kit. The former is the size of a hierarchy constructed by just adding the sum of atoms as a top element. This hierarchy may then be altered by adding a shape that covers (at most) two of the existing shapes. If this addition is repeated exhaustively, the resulting hierarchy will have the maximum size.

If a hierarchy is used to describe the materialization of a design then its elements are components of the design. Each component should be accounted for by smaller components that are its proper parts. Hierarchies, by definition, support this because every nonempty element of a hierarchy, with exception of the atoms, is the join of other elements that are its proper nonempty parts. Although necessary, this is not a sufficient condition as there are hierarchies with elements that are not accounted for by their proper parts.

For example, hierarchy in Figure 6 shows an IKEA coffee table with its two typical parts: a board and leg. The join of the two parts is the table itself, which leaves the three legs of the table unaccounted for. In order to avoid this, the components should be sums of smaller components, which leads to a special type of hierarchy in accordance with to the following definition.

Fig. 6.

The typical parts of an IKEA coffee table.

It is clear that elements of S are proper parts of x, because x = ∑S, x ∉ S, and a sum is greater or equal to any of its arguments, so that sum-reducible elements are also join-reducible. The converse does not hold, as in hierarchy in Figure 6. The difference between join-reducibility and sum-reducibility deserves a closer look.

For example, let shape a be analyzed by a discrete four-element hierarchy with three atoms x, y, and z such that a is the sum of the atoms. Shape a is both join-reducible and sum-reducible, however, where subsets {x, y}, {x, z}, {y, z}, and {x, y, z} have a as the join only the last subset has it as the sum. If we change the atoms so that x · y ≠ 0 and z = x ⊕ y, subset {x, y, z} still has a as the sum, but so do the remaining three subsets.

Join-reducibility is a general property because it depends only on the partial order among the elements involved. It is enough to inspect the Hasse diagram of a hierarchy to decide if an element is join-reducible. In contrast, sum-reducibility is an individual property because it also depends on the elements themselves.

The hierarchy in Figure 1 is summable and this should be true of any hierarchy describing the materialization of a design. We start with the smallest components of the design and build larger components from them and even larger components from these components and continue the process until the design is complete. Consequently, every component of the design consists of the smallest components that we started with, which leads to the following proposition.

The proposition (trivially) works for atoms because a ∨ a = a and a + a = a, where a is an atom. In accordance with Definition 1 a nonempty element of a hierarchy is either an atom or it covers, and it is a join of at least two and possibly more elements of the hierarchy. Some of these elements may be atoms, but the other ones are themselves joins of the elements they cover. Because join is an associative operation we may substitute these elements with the related joins of elements. We may continue with such substitutions until there are no more elements that cover other nonempty elements. At this point all of the elements are atoms and our original element is a join of atoms of the hierarchy. According to Definition 3, in summable hierarchies all of the join-reducible elements are sum-reducible, and we may use the same procedure with sums instead of joins.

The fact that the top element of a hierarchy is the join of all of its atoms comes as a corollary of the proposition above. By the same token, the top element is the sum of the atoms if the hierarchy is summable.

We conclude this account with an interesting property that unites the concepts of summability and discreteness.

In summable hierarchies an element is the sum of the elements it covers and if the hierarchy is also discrete these elements are pairwise discrete. This creates an opportunity to replace the sum of elements with their symmetric difference, because symmetric difference of discrete shapes is equal to their sum or if x · y = 0 then x ⊕ y = x + y. Definition 3 may now be reformulated as follows.

To see how Definition 4 works let us assume that x covers two elements y and z and that x = y ⊕ z. If y · z = 0 then x = y ⊕ z = y + z and x is XOR-reducible. In contrast, if y · z ≠ 0 then x = y ⊕ z = (y + z) – (y · z) so that neither y nor z are parts of x, which contradicts the original assumption that x covers y and z. This may be summarized in the following proposition.

Replacing sum with symmetric difference has a practical side: it allows for simultaneous calculations with both shapes and their boundaries, which is discussed in the next section.

2.3. Applications and constructions of hierarchies

Hierarchies that are summable and discrete are well suited for applications in design. We should explore possibilities of their use and construction with an eye on their role as shape approximations.

An XOR hierarchy is an excellent choice for representing the materialization of a design. It has a useful property of considering parts disjoint only if they are physically discrete. Such realism on the part of representation allows for an object to be really built out of parts that are the atoms of the hierarchy analyzing the object. In particular, both the object and its components are sums of atoms of the hierarchy. The atoms are pairwise discrete which prevents collisions of components and makes the hierarchy an excellent representation for the object assembling process. Finally, being discrete guarantees that the hierarchy satisfies the unique representation requirement that makes it a good shape approximation.

An XOR hierarchy has the least upper bound for every part of the object it analyzes, which renders it an excellent representation for the purpose of maintaining the object. For example, consider the hierarchy in Figure 1 as a set of replaceable parts of the table, which, just in case of a total loss, includes the table itself. Now suppose that the part in Figure 2a gets damaged by termites. The smallest among the replaceable parts that contain part (a) should be replaced in order to offset the damage. That is the part in Figure 2b that is the closure of part (a) or its least upper bound with respect to the hierarchy. This representation may be improved by assigning a set of attributes to each element of the hierarchy. Each attribute may describe a function the element performs. The sets of attributes form a hierarchy isomorphic to the original one. If the object is not performing certain functions, the smallest replaceable part capable of performing these functions should be replaced. To find the part one takes the closure of the malfunctioning attributes in the hierarchy of attribute sets and then maps it, via isomorphism, to the hierarchy of replaceable parts.

If an XOR hierarchy is considered a shape approximation, then its size matters. In hierarchy X(a) a part x of a is represented by its closure Γ(x) ∈ X(a), but this relation is many to one, there are (infinitely) many parts of a represented by the same element of X(a). This calls for an equivalence relation ≡ on parts of a such that x ≡ y if Γ(x) = Γ(y). This relation partitions the parts of a into equivalence classes corresponding to nonempty elements of X(a). The more elements a hierarchy has the more equivalence classes there are and the better it approximates the shape. However, not all of the parts of a are represented equally well in X(a). Parts that are elements of X(a) are best represented. In contrast, dense parts, or parts with closures that equal a, may be poorly represented by the hierarchy. This is especially true of small dense parts where their size is in disagreement with the fact that only a is big enough to account for all of their properties.

For example, a dense part may be constructed by picking an arbitrarily small part from every atom of X(a) and then summing these parts. The resulting part can be arbitrarily small, but its closure is a; thus, when it breaks down the whole object analyzed by the hierarchy is a total loss. If the table from our previous example is damaged so that a tiny termite damage appears on each of the legs and the board, the total damage is small, but the table is a total loss.

Shapes are approximated by their decompositions but also by their boundaries. Being one dimension lower than the shapes they delineate, boundaries are simple and economical representations. For example, in solid modeling, surface-based models represent solids indirectly via their bounding surfaces, which are also used to calculate the engineering properties of solids (Timmer & Stern Reference Timmer and Stern1980; Lee & Requicha, Reference Lee and Requicha1982). Likewise, in mathematics, many properties of three-dimensional (3-D) shapes are expressed via volume integrals. The well-known method of direct integration may then be used to represent a volume integral over a shape via the sum of simpler surface integrals over its boundary. The closely related divergence theorem of vector calculus yields a similar result.

Given the importance of shape boundaries it would be advantageous for any decomposition acting as a shape approximation to take account of the boundaries of its elements. XOR hierarchies are well suited for that because, in accordance with Definition 4, their reducible elements are symmetric-difference reducible and symmetric difference has an interesting property that ties shapes and their boundaries.

Proposition 4 does not apply to all of the shapes but to a special class of shapes: diagonal shapes. The latter are defined in an algebra U_ii where shapes and the space in which they are manipulated are of the same dimension i = 0, 1, 2, or 3. Such are the solids in 3-D space or planar segments in a plane, which are expressive enough for most design (engineering) applications. The former pertain to the models designers build, including 3-D computer-aided design models, while the latter relate to 2-D drawings, which are traditional representations in design.

Figure 7 illustrates Proposition 4. XOR hierarchy (a) analyzes a double square defined in U ₂₂ algebra, which manipulates planar segments in a plane. The symmetric difference of the two squares, which are the atoms of the hierarchy, yields the double square and so does their sum. In contrast, the symmetric difference of the boundaries of the atoms defined in U₁₂, which manipulates lines in the plane, yields the boundary of the double square (b), but their sum, shape (c), is greater than the boundary, because it contains a line that divides the double square.

Fig. 7.

The sum and symmetric difference hierarchy: (a) with the top element being the sum or the symmetric difference of the atoms, (b) the symmetric difference, and (c) the sum of the boundaries of the atoms.

To account for both shapes and their boundaries a hierarchy has to be XOR with elements that are ordered pairs of shapes paired with their boundaries. The pairs are combined with a single operation of symmetric difference in the framework of UB_i algebra (i = 1, 2, or 3), which is closed under Euclidean transformations that act on the pairs (Krstic, Reference Krstic2001). Note that because points have no boundaries there is no UB₀ algebra. The operation is applied componentwise in the following way.

Let b be an operator that takes shape a defined in U_ij to its boundary b(a) in U_ij−1 and let x and y be diagonal shapes so that pairs (x, b(x)) and (y, b(y)) are defined in a UB_i algebra. The symmetric difference of the two pairs is

Because x and y are diagonal shapes Proposition 4 applies to yield

If x and y belong to an XOR hierarchy, and are covered by the same element, then they are discrete and symmetric difference has the effect of a sum. The computation above is as follows:

The computation starts with a sum, as if modeling an assembling process, which is then recast as the symmetric difference in order to preserve shape boundaries in computation. After the computation the two symmetric differences appearing in the result are recast back to sums for their intuitive appeal.

We will now turn our attention to some of the constructions available for XOR hierarchies.

Complex hierarchies may be obtained from the simpler ones. This is especially easy to do with XOR hierarchies. Let a_i, i = 1, 2, … , n be a finite family of pairwise discrete shapes and let X(a_i) be a family of XOR hierarchies that analyze these shapes. The union of family X(a_i) augmented by the sum of family a _i is a complex XOR hierarchy that analyzes the latter sum.

(1)

Formula (1) may be used recursively to build complex hierarchies from the simpler ones. This is similar to what we do when we construct hierarchical file structures on our computers by dragging already populated file folders into an empty file folder.

The construction of hierarchies may also go in the other direction and derive smaller hierarchies from the bigger ones. The simplest of such constructions is based on the fact that all the elements that are parts of any reducible element of a hierarchy form a hierarchy themselves. This hierarchy is a subhierarchy of the original hierarchy.

If, for example, the process of assembling an object a is described by hierarchy X(a), then the same process for a component b ≤ a, b ∈ X(a) is described by the subhierarchy X(b) ⊆ X(a) generated by b and defined by X(b) = {x ≤ b | x ∈ X(a)}. Using this construction the process of manufacturing an object may be divided into separate processes of manufacturing its components that then may be done concurrently.

The construction above works well for the components of an object. If, in contrast, the goal is to manufacture a new object that is a part, but not a component of the original object, then subhierarchies do not work. There is another possibility that relies on the relativization of the structure of an analyzed shape to one of its parts.

For example, the hierarchy in Figure 8d is a decomposition of the shape (a) that has shape (b) as a part. Decomposition in Figure 8e is the relativization of the original hierarchy to shape (c). Note that the relativization is also a hierarchy, but this may not always be the case. There are summable or discrete hierarchies with relativizations that fail to be hierarchies. In contrast, XOR hierarchies behave in accordance with the following result.

Fig. 8.

The hierarchy construction: (a) shape and (b, c) its parts and, hierarchy (d) of (a) is changed by combining hierarchy (e), which is the relativization of (d) to (b), and hierarchy (f), which is the relativization of (d) to (c), to produce hierarchy (g).

Proposition 5 describes yet another nice property of XOR hierarchies that may be used to facilitate a transformation of one hierarchy into another. If some facilities are used to assemble an object according to some XOR hierarchical decomposition of the object, then the same facilities may be used to assemble a new object, which is a part of the original object, in accordance with the relativization of the original hierarchy to this part.

This may be carried a step further to allow for the changing of components of the original hierarchy. The hierarchy may be changed to recognize a shape that is not its element, but is a part of the shape the hierarchy analyzes. Let X(a) be an XOR hierarchy and shape b ∉ X(a) be a part of shape a. Relativization X(a)/b is an XOR hierarchy and so is X(a)/(a − b). Because the sum of b and a − b is a, identity (1) may be used to combine X(a)/b and X(a)/(a − b) in a new hierarchy X′(a), or

(2)

For example, in Figure 8 hierarchy (d) of shape (a) is changed by taking hierarchy (e), which is the relativization of hierarchy (d) to shape (b), and hierarchy (f), which is the relativization of hierarchy (d) to shape (c), and combining them in accordance with (1) to get a new hierarchy (g).

Construction (2) allows for the components b and a − b to be assembled via the same facilities that are used to assemble a according to X(a). In contrast, assembling a from b and a−b according to X′(a) requires new facilities.

Formula (2) may be used recursively to gradually change a hierarchy by adding new parts either to the original hierarchy or to any of its subhierarchies.

3.1. Definition

Consider the hierarchy in Figure 4 as a decomposition of shape (a) defined in U₂₂. The latter is a shape algebra that manipulates planar segments in a plane. Note that Figure 4 also contains lines, dashed lines, and labels. Algebras for these would be needed as well, however, for our argument U₂₂ alone will do.

Shape (a), which is analyzed by the decomposition, is its member, but also is the sum of the other members, shapes (b) through (k). Therefore, the decomposition represents a set of spaces of a house together with their sum, which is the plan of the house. Some other sums of interest are also included, like shapes (b) and (c) that represent the public and private spaces of the house.

There are reasons for including even more sums. For example, one may consider a middle section of the plan, which has no access to the perimeter walls. The area is bounded by the grid lines 3, 5, b, and d as shown in Figure 9a. Any space in need of artificial lighting and ventilation is a part of that shape. Such are the kitchen, bathroom, and closet. Their sum in Figure 9b may be included (in the decomposition) as it conveniently enumerates all the spaces with such a need. This shape becomes the greatest element that is a part of the shape in Figure 9a, or the greatest lower bound of that shape. Any part of the design may become interesting at some point in the design process. For every such part the decomposition should contain the greatest lower bound. Consequently, all of the sums have to be included and the decomposition is closed under the sum of U₂₂. The advantages of this structure are twofold.

Fig. 9.

The Ohlenbusch residence: (a) a middle section of the plan with no access to the perimeter walls and (b) the sum of the kitchen bathroom and closet.

First, it allows for the properties of any part of the design to be assigned to the appropriate elements of the decomposition. In the above example the properties of shape in Figure 9a are assigned to the kitchen, bathroom, and closet, labeling them as spaces in need of artificial ventilation and lighting.

Second, the structure comes in handy if a part of a design has to be defined in terms of properties that are recognized by the decomposition. For example, the shape in Figure 9a contains or has the properties of the kitchen, bathroom, and closet. This can be determined for every part of the design because there is a greatest lower bound for every such part.

To explore conjunctive combinations of elements of the decomposition we rely on the product operation from U₂₂ algebra. For example in Figure 10, the product of shapes representing the kitchen (c) and bathroom (b) yields the shape (e), which represents the partitioning wall between the two spaces. Likewise, the product of shapes representing the bathroom (b) and closet (a) yields the partitioning wall (d). Taking products of adjacent spaces exhaustively enumerates such walls. The decomposition becomes a system of spaces together with partitioning walls between them. Further, products of shapes representing walls are joints between the walls.

Fig. 10.

The Ohlenbusch residence: (a) closet, (b) bathroom, and (c) kitchen; partitioning walls between (d) the bathroom and closet and (e) the kitchen and bathroom; and (f) the joint of walls (d) and (e).

For example, in Figure 10 shape (f) is the product of shapes (d) and (e). The latter shapes represent walls that makes (f) the joint between the walls. The decomposition now becomes a system of spaces, partitioning walls, and joints between the walls. Its structure is that of an algebra with respect to the sum, and a partial algebra with respect to the product. The fact that it has products rules out the possibility of the structure being a hierarchy.

Further elaboration of the design may require some additional constrains on the structure of the decomposition.

Suppose that the door between the bedroom and garage is to be removed and replaced with a wall. The smallest element of the decomposition altered by this action is the wall between the two spaces. It includes the door and is the least upper bound of the door with respect to this decomposition. To allow for a change of an arbitrary part of a design its decomposition should have the least upper bound for every such part. Consequently, the decomposition should be closed under products, which elevates its structure to an algebra closed under both sums and products.

Every part of the design is represented by the two distinguished elements of the decomposition. These are the least upper bound of the part and its greatest lower bound. The part is bounded by the two and has at least the properties of the latter element and at most the properties of the former one. The unique representatives are provided regardless of the fact that there are infinitely many parts while the decomposition is only finite. However, the decomposition need not be small. In our example, it has over 2000 elements, and we may include some new elements like, say, complements of the elements we already have.

Complements deserve a closer look. As discussed elsewhere (Krstic, Reference Krstic and Gero2004, Reference Krstic2005) we perceive a shape as a whole, but we break it down into parts to understand or explain it. We assign properties to the parts and tend to see the properties of the whole as the sum of the properties of the parts. This makes finding the complement of a part an easy task: just take the shape that has all of the properties of the whole but none of the properties of the part. Unfortunately, shapes usually do not meet our Boolean expectations.

For example, the complement of the kitchen should, in a Boolean fashion, consist of all the spaces of the house but the kitchen. Algebra U₂₂ has a difference operation to support the creation of complements. The shape in Figure 11a is the complement of the kitchen obtained by subtracting the latter from the plan. It contains the bedroom and stairway, which are the only spaces that have no common walls with the kitchen. This shape is clearly not the complement we expected. It lacks the garage, bathroom, corridor, and living room.

Fig. 11.

The Ohlenbusch residence: (a) complement of the kitchen, (b) the outside space, and (c) the living room facade walls.

In another example, we may try to determine the façade walls of, say, the living room. These are partitioning the outside space from the living room and, following the logic of the construction of partitioning walls, may be determined as the product of the two spaces. The outside space should be the complement of the sum of the inside spaces. Unfortunately, this complement is the empty shape here. Our entity is not a system of inside spaces surrounded by the outside space, but a system of walls, and only in the decomposition certain combinations of walls emerge as spaces. Consequently, complement is of no help in specifying the outside space. The latter has to be defined in the same fashion as all other spaces, as a combination of walls (Fig. 11b). The product of the living room and the outside space is the shape in Figure 11c, which represents the façade walls of the living room.

Although the two examples show that complements are not essential in dealing with spatial entities there may be other compelling reasons for not using them. In an early, exploratory, stage of the design process designers may focus on developing certain parts of their designs while having only a vague notion of the other parts or the whole. Consequently, the complements may not be available at this stage. Without the complements we are left with an algebra which has the whole (the shape it analyzes) and zero (the empty shape), and is closed under + and · of U_ij. This is the same structure as that of the closed (open) sets of a topological space that motivates introduction of the topologies for shapes.

3.2. Properties of topologies

Topologies for shapes were introduced by Stiny (Reference Stiny1994) to study the continuity of shape computations. In contrast, we examine here how they may be used in place of shapes, as shape approximations.

A topological decomposition of a shape satisfies the unique representation requirement by providing for each part of the shape a pair of elements that bounds it. This is a far better representation than the one provided by hierarchical decompositions where elements, at best, top the shape parts. Topological decompositions of shapes have many interesting properties, but we will examine only those that pertain to topologies being used as shape approximations.

Because topology T(a) is closed under + and · it has the least upper bound and the greatest lower bound for every part of a. The two bounds define a topological closure Γ and a topological interior Ω operators on a set B(a) of all parts of a such that T(a) is their image, or T(a) = Γ(B(a)) = Ω(B(a)).

Stiny (Reference Stiny1994) defines topology T(a) as a set of closed elements of Boolean algebra B(a) that has been elevated to a closure algebra by the addition of a closure operator Γ. Stiny allows for topologies to be infinite, but requires for each part x of a an existence of a smallest element in T(a) that contains x as a part. This requirement is weaker than the standard requirement for a topology to be closed under all products, finite and infinite. Because B(a) is not a complete Boolean algebra there is no guarantee that all of its infinite subsets have products, so the stronger requirement does not hold in infinite topologies for shapes. A topology that only satisfies the weaker requirement cannot be generated by a given subbase in a usual way. Because this construction plays an important role in applications, we will restrict ourselves to finite topologies only, in accordance with Definition 6 above.

For example, we constructed the topology of the Ohlenbusch residence from a subbase consisting of spaces in Figure 4d–k. We later modified the subbase by adding a shape representing the outside space (Fig. 11b). This resulted in a bigger topology that included the original one.

A topology generated by a subbase is the smallest among the topologies containing the subbase: all of the topologies containing the subbase contain this topology as well.

There is a simple procedure for generating a topology from a subbase (see, e.g., Vickers Reference Vickers1989, p. 32), but it may not be practical to keep all of the elements of a topology at all times. Even small designs may have big topologies like the topology in our example, which has over 2000 elements. It should be sufficient to keep the most important elements and construct the other elements as needed. In our example, the original spaces, which form the subbase, should be kept and we may also keep some other shapes like the walls and joints between the walls. We need to be able to construct the relevant elements to uniquely represent an arbitrary part of the analyzed shape. These are the closure and interior of the part, which could both be constructed directly from the subbase via the following procedure.

For example, in Figure 12 shape (a), defined in U₂₂ algebra, is analyzed via topology (b) generated by subbase (c). Shape (d) is a part of (a) and its closure is shape (e). To construct (e) we take the relativization (f) of the subbase to shape (d) and construct the sets C ₁, C ₂, and C ₃, which are a singleton (g), a set (c), and a singleton (i), respectively. Shapes (g), (h), and (i) are the products ∏C ₁, ∏C ₂, and ∏C ₃, respectively, and their sum is the closure (e).

Fig. 12.

Closure construction: (a) shape; (b) its topology with (c) the subbase; (d) a part and (e) its closure; (f) relativization of (c) to (d); (g, c, i) sets C ₁, C ₂, and C ₃ with (g, h, i) their products, which sum to (e) the closure.

Note that Procedure 1 above provides for a direct construction of both Γ(x) and Ω(x). We do not construct one and then use standard topological identities

(3)

to get the other. The identities above define operators that (in general) differ from Ω and Γ. If we consider T(a) as a set of closed parts of a then it is the image of Γ. Its complement T(a)′ = {a} – T(a) is the set of open parts of a and the image of Ω _Γ. Dually, T(a) may be seen as the image of Ω, which makes it a set of open parts of a. The related set of closed parts is then the image of Γ _Ω and the complement of T(a). Operators Γ and Ω define two different topologies on Β(a) except when T(a) has the structure of a Boolean algebra. In that case, Γ = Γ _Ω, Ω = Ω _Γ, and Γ and Ω belong to the same topology.

One of the reasons we dropped the complements was that they may not be available in the early stages of a design process. In contrast, complements may play a role later in the process when properties of design(s) are better understood. We may then use T(a) and its complement T(a)′ concurrently to represent/bound the shape parts. This is done by paring any of the two closures with any of the two interiors so that any of the four combinations (Γ, Ω), (Γ, Ω _Γ), (Γ _Ω, Ω), or (Γ _Ω, Ω _Γ) may be chosen to best fit a particular part.

Another important use of the complements may arise in the final phases of the design process when designs are specified for production. Such a specification usually sports a kit of discrete parts from which to build a design as well as some details on how this should be done. This means that we need a discrete decomposition of a shape that can then be extended to a hierarchical decomposition to show how the original discrete parts are put together to build the shape. There is no guarantee for topology T(a) to be atomic so it may not contain a discrete decomposition of a. To get one we need to extend T(a) to a Boolean algebra in accordance with the following definition.

It is also a topological decomposition because it contains 0 and a and is closed under · and + of U_ij. In addition, T _Bool(a) is closed under the formation of complements, which is equivalent to being closed under – of U_ij. Because T _Bool(a) is finite Boolean algebra, it is atomic and its set of atoms A is a discrete decomposition of a. Set A is the smallest, in terms of its cardinality, discrete decomposition of a such that all of the nonempty elements of T(a) may be constructed as sums of elements of A. Moreover, all nonempty elements of T _Bool(a) are sums of atoms from A and they enumerate such sums. Because nonempty elements of XOR hierarchies are sums of their atoms (by Proposition 2 and Proposition 3), an arbitrary XOR hierarchical decomposition of a, which has A as the set of atoms, can be embedded in T _Bool(a). This renders T _Bool(a) the least upper bound of all of such hierarchies. Note that, unlike Boolean algebras, hierarchies are not uniquely determined by their atoms so that there are many XOR hierarchies with A as the set of atoms.

As with T(a), it is not practical to keep all of the elements of T _Bool(a) when we may only need some important ones and the ability to construct the set of atoms of T _Bool(a) as well as the closure and interior for any part of a. A procedure for constructing the set of atoms of T _Bool(a) is as follows.

For example, topology T(a) in Figure 12b is extended to a Boolean algebra T _Bool(a) by including the shapes delineated by dashed lines. The set of atoms of the extension is given in Figure 13. Note that in this particular example the union of T(a) and its complement T(a)′ is T _Bool(a). Usually the latter algebra is greater than this union.

Fig. 13.

The set of atoms of the Boolean extension of topology in Figure 12b.

Closure and interior of an arbitrary part x of shape a with respect to topology T _Bool(a) may be obtained in accordance with the following result.

Proposition 6

Let a be a shape, x its part, T(a) a topology on a, Γ and Ω closure and interior operators from T(a), and T_Bool(a) the Boolean extension of T(a). Closure and interior of x with respect to T_Bool(a) are

(4)

respectively.■

Because x is a part of both Γ(x) and Γ _Ω(x) it is a part of Γ(x) · Γ _Ω(x) so that the latter is an upper bound of x in T _Bool(a). We need to show that there is no such shape y that satisfies the following conditions y ∈ T _Bool(a), y ≥ x and y < Γ(x) · Γ _Ω(x) (‘) so that Γ(x) · Γ _Ω(x) is indeed the least upper bound. Because T _Bool(a) is closed under – and contains T(a) it also contains T(a)′ so that either y ∈ T(a) or y ∈ T(a)′ or y is a new element that does not belong to any of the topologies. If y ∈ T(a), then y ≥ Γ(x) and if y ∈ T(a)′, then y ≥ Γ _Ω(x) in any case y ≥ Γ(x) · Γ _Ω(x) so that y is not the least upper bound of x. If y is a new element then it is a combination of two elements u ≥ x and v ≥ x, from one or both of the topologies. The possible combinations are

1. a. y = u + v, where u ∈ T(a), v ∈ T(a)′,

2. b. y = u · v, where u ∈ T(a), v ∈ T(a)′,

3. c. y = u − v, where u ∈ T(a), v ∈ T(a)′, and

4. d. y = u – v, where u, v ∈ T(a).

Other possible combinations are either symmetrical to the ones above or yield elements already in T(a) or T(a)′. First, we show that there is no y obtained in combinations a to d, such that y satisfies (′). Combination a gives y ≥ u ≥ Γ(x) ≥ Γ(x) · Γ _Ω(x). In b case u ≥ Γ(x) and v ≥ Γ _Ω(x) so that y = u · v ≥ Γ(x) · Γ _Ω(x). Combination c yields y = u – v = u · (a – v). Because both u and (a – v) belong to T(a), so does their product y and y ≥ Γ(x) · Γ _Ω(x), as shown earlier. Finally, case d is the same as b because y = u − v = u · (a − v), where u ∈ T(a) and (a − v) ∈ T(a)′. This proves that Γ _Bool(x) = Γ(x) · Γ _Ω(x), which with (3) results in Γ _Bool(x) = Γ(x) · (a − Ω(a − x)). The proof of the second identity of the proposition is a dual of the proof above.

Both Ω _Bool and Γ _Bool are expressed, in Proposition 6, in terms of Ω and Γ. Because the latter operators may be constructed from the subbase B via Procedure 1 construction of Ω _Bool and Γ _Bool is feasible.

We conclude this section with some counting to find out how big our structures may get. The size of any finite Boolean algebra including T _Bool(a) is 2^k, where k is the number of atoms of the algebra. The latter number for T _Bool(a) depends largely on the subbase B of T(a), in accordance with Procedure 2 above. The size n of B matters, but also do the relations among its elements. In the maximum case, the only relation between the elements of B is ∑B = a. Each shape x_i, from Procedure 2, then yields a different atom so that the number of atoms of T _Bool(a) is k = 2ⁿ − 1. In the minimum case, the only elements of T _Bool(a) are these of B, or T _Bool(a) = B. Consequently, n = 2^k, so that the number of atoms is k = log₂n. We mentioned earlier that discrete (and by extension XOR) hierarchies with k atoms may range in sizes between k + 1 and 2k − 1. This means that the simplest hierarchies embedded in T _Bool(a) will have between log₂n + 1 and 2 log₂n − 1 elements, whereas the most complicated ones will have between 2ⁿ and 2ⁿ⁺¹ − 3 elements.

For example, in Figure 12 topology (b) generated by a three-element subbase (c) has the Boolean extension with four atoms depicted in Figure 13. This is less than the maximum seven because there are more relations than ∑B = a among the shapes of the subbase. In particular, products of different shapes of the subbase are equal. Similarly, the Ohlenbusch residence topology has been constructed from a subbase consisting of eight spaces, as shown in Figure 4d through 4k. The Boolean extension of such a topology may yield a maximum of 255 atoms. In contrast, we have here only about one-tenth of that number because of the numerous relations among the elements of the subbase.

3.3. Parts and elements

Because shape parts are represented via elements of topologies, the relation between the parts and elements is crucial to the understanding of how (well) shapes are approximated with the topologies.

For example, if some part x of shape a is examined so that the structure imposed on a by topology T(a) is respected, then it is safe to say that x is Ω(x). Part x has the properties of Ω(x) and there is no other shape like this one in T(a) that is greater than Ω(x). The part may have some other properties as well, but those are not recognized by T(a). If, in contrast, the place of x in the structure of T(a) has to be determined, then x is Γ(x). Closure Γ(x) accounts for all of the properties of x and is the least such element of T(a). The closure may have some properties that x lacks, but T(a) is oblivious to that.

For an arbitrary part x of shape a represented by Ω(x) and Γ(x) in T(a) there may be (infinitely) many parts of a with the same representation in T(a). This justifies the introduction of an equivalence relation ≡ such that x ≡ y if and only if Ω(x) = Ω(y) and Γ(x) = Γ(y), where x, y ≤ a. If x is an element of T(a), then Ω(x) = Γ(x) = x and equivalence class [x]_≡ has only one element x. In contrast, when x is not an element of T(a) class [x]_≡ has infinitely many elements provided that x is not made of points only.

Number n _≡ of equivalence classes modulo ≡ indicates how well T(a) approximates a. This number in the case of the smallest (trivial) topology {0, a} is 3. It appears that the trivial topology is not a bad shape approximation after all. It shows that a is nonempty, that it contains 0 and itself, and has proper parts as well. The following result provides some insights in the possible sizes of n _≡.

In case x = y there is a one-element equivalence class [x]_≡. To show the same for x < y it is enough to construct a shape z such that Ω(z) = x and Γ(z) = y. We start with T _Bool(a), which is an atomic Boolean algebra with elements that are sums of atoms. Shape y − x is an element of T _Bool(a) and is the sum of some set of atoms A. We now construct a set B by taking a nonempty proper part from each of the elements of A, or B = {p | p < q, p > 0, q ∈ A}. Shape z = x + ∑B satisfies both Ω(z) = x and Γ(z) = y. The former because any shape u ∈ T(a), such that x < u ≤ y, contains at least one atom from A so that z ≥ u does not hold, and the latter because any shape v ∈ T(a), such that x ≤ v < y, misses at least one atom from A so that z ≤ v does not hold. Note that there are infinitely many choices for picking proper parts of atoms from A, when constructing B, so that there are infinitely many shapes in [x]_≡, provided that a is not made of points.

In a topology that is a chain every pair of different elements is comparable so that for an n-element chain n _≡ = n (n + 1)/2. This establishes the upper bound for n _≡. The lower bound is difficult to establish, but it is clearly greater than 3n − 3 because for each x ∈ T(a) there is at least three classes, a one-element class [x]_≡, a class defined by x and 0, and one defined by a and x. Judging by the number of equivalence classes it seems that an n-element topology is much better shape approximation than an n-element hierarchy which only has n of such classes.

As with hierarchies, not all parts of a are equally well represented by topology T(a). The elements of T(a) are the parts that are best represented. They are represented by themselves. In contrast, parts that are both boundary, defined by Ω(x) = 0, and dense are the worst represented ones. Such parts have no recognizable properties despite the fact that only a is big enough to account for all of their properties. No matter how well a topology approximates a shape there will be infinitely many of such parts in accordance with the following corollary of Proposition 7.

In accordance with Proposition 7 there is a nonempty equivalence class defined by shapes 0 and a, which are comparable. An element x of this class is both dense and boundary because Γ(x) = a and Ω(x) = 0. There are infinitely many such parts in accordance with the last note of the proof of Proposition 7.

Although poorly represented, dense and boundary parts are well analyzed by the topology.

For example, the shape in Figure 14a is both dense and a boundary part of the shape in Figure 12a with respect to the topology in Figure 12b. The shape is, thus, poorly represented in the topology. In contrast, the topology in Figure 14b is the relativization of the topology in Figure 12b to the shape in Figure 14a and the two topologies are isomorphic. Consequently, the shape in Figure 14a and the shape in Figure 12a are analyzed by the original topology in the same way. Note that, not unlike XOR hierarchies, the structure of topologies is preserved under relativization.

Fig. 14.

(a) A part of the shape in Figure 12a, which is both dense and a boundary with respect to the topology in Figure 12b, and (b) the relativization of the topology to shape (a).

We may assume that each part x of a is, de facto, approximated by the elements of T(a) that represent it. Thus, we may calculate errors that such an approximation introduces. If x is approximated by Ω(x) the error is

(5)

whereas an approximation by Γ(x) introduces the error

(6)

Shapes that are elements of topologies are the most closely approximated ones, if x ∈ T(a) then ɛ_Ω(x) = ɛ_Γ(x) = 0. In general, if x and y are parts of a and ɛ_Ω(x) ≤ ɛ_Ω(y), then x is approximated by Ω(x) at least as well or better than y.

An interesting way of examining errors (5) and (6) is from the viewpoint of the topology itself. Because both ɛ_Ω(x) and ɛ_Γ(x) are parts of a we may approximate them using different closures and interiors. A simple exercise in closure/interior arithmetic yields some interesting results.

For example, the Γ closure of ɛ_Γ(x) is

(7)

which is the smallest element of T(a) that is greater than error ɛ_Γ(x). The error cannot be greater than (7). Note that both error (6) and its closure (7) may be defined for XOR hierarchies because the latter are closed under Γ.

The Ω interior of ɛ_Γ(x) is denoted by σ(x) so that

(8)

The error cannot be smaller than σ(x), which is the greatest element of T(a) with a following property: is a part of Γ(x) and has no common parts with x. If T(a) is a set of replaceable parts of some object and some part x breaks down, Γ(x) will be replaced. Then again, because σ(x) and x do not share parts the former shape may be recycled. If a is a car, Γ(x) its alternator with a bad coil x, then the repair shop uses T(a) to pinpoint and replace the alternator. The old alternator goes to a remanufacturing facility as a “core.” At the facility σ(x) is used to find out which parts could be salvaged when rebuilding the alternator. Shape σ(x) is the core of x with respect to T(a) or the reusable part of Γ(x).

As we have shown earlier, XOR hierarchies may be used the same way topologies are, as sets of replaceable parts for the maintenance purpose. In contrast, the concept of reusable part or core is foreign to hierarchies because their lack of the interior operator. This gives topologies an advantage over hierarchies in such applications. One can imagine a hierarchy, embedded in T _Bool(a), that would recognize the core of the alternator, but such a hierarchy would also recognize its other components that will make it much bigger than T(a). This hierarchy will do for assembling the car, but is too complicated for maintaining it.

Because closure Γ _Ω yields the complement of T(a), we may take the closure of ɛ_Γ(x) and then the complement of the result. This is another interesting shape and we will denote it by μ(x) so that

(9)

This is the greatest element of T(a) that does not have common parts with ɛ_Γ(x). It has only those parts of Γ(x) that are also parts of x. If attention is paid to μ(x) and its parts only, then it does not matter whether x or its approximation Γ(x) is used. From the point of view of μ(x) we make no error when approximating x is with Γ(x). This shape becomes a if x is an element of T(a).

Similarly, the complement of the Γ _Ω closure of ɛ_Ω(x) is

(10)

This is the greatest element of T(a) that does not have common parts with ɛ_Ω(x). From the point of view of this shape, there is no error if x is approximated with Ω(x). This shape becomes a if x is an element of T(a).

Because μ(x) is included in shape (10) their product is μ(x). The latter is the greatest element of T(a) for which it does not matter whether x or any of its approximations is used. The greater μ(x) is, the better the topology approximates the part. We may use μ(x) as a measure of that approximation. Note that μ(x) = a, if x is an element of T(a) and μ(x) = 0, if x is both dense and boundary part of a with respect to T(a). This measure cannot be defined for hierarchies, which makes it is hard to decide if a part is well approximated by a hierarchy.

The closure Γ of ɛ_Ω(x) is

(11)

The error cannot be greater than this element of T(a). In contrast, the error cannot be smaller than

(12)

Identity (12) renders ɛ_Ω(x) a boundary part of a with respect to T(a). Similarly, Ω _Γ(ɛ_Γ(x)) = 0 renders this error a boundary part of a, but with respect to a different topology T(a)′.

The last of the possible combinations of the errors and operators is the complement of Ω _Γ(ɛ_Ω(x)):

(13)

This shape, although an element of T(a), is related to its complement T(a)′. It is the complement of the core of (a − x) with respect to T(a)′.

Finally, the two errors are bounded by the elements (12), (11), (8), and (7) of T(a), so that

(14)

Those elements approximate (represent) errors ɛ_Γ(x) and ɛ_Ω(x) in T(a). The second of inequalities (14) may apply to XOR hierarchies, however, with a trivial lower bound.

(15)