2.1. Set algebras of decompositions

If parts recognized in decompositions are paramount in computations, combining decompositions as sets is a viable option. Set operations of union, intersection, and difference may be taken as sum, product, and difference of decompositions. The operations preserve the set elements, and set inclusion establishes the ordering on Δ_ij. However, set Δ_ij of decompositions is not closed under ∩ and −. The intersection or difference of two decompositions may be empty, but there is no empty decomposition; a decomposition contains at least one shape, which may be 0. The set Δ_ij has to be augmented with the empty set to become an algebra.

Definition 5. A set algebra of decompositions D_ij satisfies Definition 4 and has the set Δ_ij ∪ {Ø} together with operations ∪, ∩, and − as the Boolean part, whereas its group part is the same as that of U_ij. █

This algebra, which was introduced by Stiny (1990, 1994), treats shapes that are elements of decompositions as symbolic objects without further dividing or summing them. The algebra works well if shapes have predetermined parts that remain fixed throughout a computation. The result of the computation contains only shapes that are elements of decompositions entering the computation. These are the atoms of the computation. For example, decompositions in Figure 4a, b, and c are respective sum, product, and difference of decompositions in Figure 3 computed in the framework of D_ij. Note that no new shape has been created in the computations.

Computing in D12: (a) sum, (b) product, and (c) difference of decompositions in Figure 3.

2.2. Complex algebras of decompositions

Set algebras compute with shapes as they would with any other object. Properties of shapes are irrelevant in D_ij. In contrast, shape properties, in particular spatial properties, are most important in design. An algebra of decompositions that aspires to be an algebra of analyzed shapes should take into account spatial properties of shapes that are elements of decompositions. This can be achieved by letting the elements of one decomposition combine with the elements of another decomposition in computations. With no special preference, these combinations may be taken exhaustively. The operations of such an algebra are no more than extensions of shape operations (+, ·, and −) to direct products of decompositions.

Let A and B be two decompositions, then their sum +′ is defined as A +′ B = +(A × B). “Polish” notation used here is an elegant way of writing A +′ B = {x + y| x ∈ A, y ∈ B}. The other two operations product ·′ and difference −′ follow as A·′B = · (A × B) and A −′ B = −(A × B).

Because decompositions are finite subsets (complexes) of some algebra of shapes U_ij, they may be seen as elements of a complex algebra

constructed on U_ij. The algebra operates on the set

with the set of all decompositions Δ_ij as a subset. The latter set is precisely the set of all finite complexes and forms a subalgebra in

. The general rule for operations of complex algebras (Gratzer, 1979) yields operations +′, ·′, and −′ as defined above.

Decompositions are ordered by ≤′ defined in accordance with the general definition for relations of complex structures (Gratzer & Whitney, 1978). That is, A ≤′ B, if for every x ∈ A there exists y ∈ B, such that x ≤ y, and for every y ∈ B there exists x ∈ A such that x ≤ y.

The set Δ_ij has a lower bound under the ordering ≤′. It is the decomposition of the empty shape {0}. However, Δ_ij does not have an upper bound.

Definition 6. Complex algebra of decompositions

satisfies Definition 4 and has the set Δ_ij together with operation +′, ·′, and −′ as the Boolean part, whereas its group part is the same as that of U_ij. █

The new algebra handles shapes as spatial objects, not unlike U_ij. For example, decompositions in Figure 5a, b, and c are the respective sum, product, and difference of decompositions in Figure 3 when computed in the framework

. Note that the resulting shapes differ from the input ones: the former are combinations of the latter.

Computing in : (a) sum, (b) product, and (c) difference of decompositions in Figure 3.

3.1. Properties of set algebras of decompositions

Set algebras for decompositions compare favorably with shape algebras. All of the important properties of the latter, such as distributive and idempotent, are preserved by the former algebras. However, set algebras are less successful in satisfying minimum and additional requirements.

The minimum requirement holds for sums, but not for products and differences.

It is not possible to decide, by using operations and the relation of D_ij, whether two of its different elements are decompositions of the same shape. The algebra sees decompositions as sets of shapes (Definition 1), rather then decompositions of shapes (Definition 2). It manipulates elements of decompositions as symbols disregarding their spatial properties.

This renders D_ij an unlikely choice if computations with analyzed shapes are an objective. However, D_ij is not without design applications.

Set algebras work well in situations where design is restricted to a finite kit of discrete parts, such that all shapes of interest are simple sums of the parts. Designing in the framework of a building system is a good example. Such systems usually offer kits of prefabricated building parts that may be assembled to produce a variety of buildings. Parts may range from structural members, like bearing walls or ceiling slabs, to architectural elements, such as partitions or facade articulations.

The set of all subsets of such a kit is a subalgebra of D_ij, which is isomorphic with a certain subalgebra of U_ij.

Let K_ij be a finite set of pairwise discrete shapes (no two of its elements share parts),

the set of all of its subsets, and

the set of shapes obtained by summing the elements of

. Because elements of K_ij are pairwise discrete shapes, combining them in products and differences yields no new shapes except for the empty shape. For example, if a, b ∈ K_ij and a ≠ b, then a · b = 0 and a − b = a, if a = b, then a · b = a and a − b = 0. New shapes can only be produced in sums so that

is the set of all shapes that could be created from the shapes of K_ij. In contrast, set

enumerates all of the decompositions of the former shapes into the latter ones. Mapping Σ that connects the two sets has some interesting properties.

Lemma 1. Mapping Σ from

is a bijection. █

Because

is an image of

, Σ is a surjection. To prove that Σ is an injection (one to one) we assume the opposite: there are two distinct decompositions in

that analyze the same shape in

. For the assumption to hold, there has to be at least one shape that is an element of one of the decompositions, but not an element of the other one. Say, decompositions A and B both analyze some shape a, and shape x is an element of A, but not of B. Consequently, x is a part of Σ A, but not of Σ B. The latter holds because x does not share parts with any of the elements of B because they all belong to K_ij and so does x. However, Σ A = Σ B = a, which leads to a contradiction rendering x both a part of a and not part of a. This refutes the assumption rendering Σ an injection. Because Σ is both a surjection and an injection it is a bijection, which completes the proof.

Sets

are closed under set operations of D_ij, and shape operations of U_ij, respectively. They are Boolean parts of the two new algebras: decomposition algebra

and shape algebra

. The two new algebras are isomorphic in accordance with the following proposition.

Proposition 2. Algebras

are isomorphic. █

The isomorphism is framed by the bijection Σ. We only need to show that Σ preserves the operations of algebras. Sum is preserved because a + b = Σ A + Σ B = Σ(A ∪ B), where a and b are shapes from

and A and B are their respective decompositions from

. The same can be shown for product and difference to complete the proof of the proposition.

The new kit of parts algebra

computes with analyzed shapes in a meaningful way even though it does not see them as spatial objects. In formal design theory

algebras are used in systems like set grammars (Stiny, 1982) or structure grammars (Carlson et al., 1991), which work with predefined vocabularies of shapes. These systems have the same computational power as shape grammars and produce languages of designs similar to that generated by shape grammars. However, they cannot handle the emergence and ambiguity of shapes, which are important in creative phases of a design process. In contrast, shape grammars do that well (Knight, 2003a, 2003b).

3.2. Properties of complex algebras of decompositions

Unlike set algebras, complex algebras for decompositions do not preserve important properties of U_ij algebras. There are two reasons for this.

First, it is known in universal algebra that the identities r = s valid in an algebra are also valid in its complex counterpart if and only if individual variables occur only once in both r and s (Guatam, 1957; Bleicher et al., 1973; Shafaat, 1974). However, most of the important identities of U_ij are not of this kind. In particular, these defining idempotent, a + a = a, a · a = a, and distributive property, a · (b + c) = (a · b) + (a · c), a + (b · c) = (a + b) · (a + c) are valid in U_ij, but not in

.

Second, the relation ≤′ is not a partial order, but a preorder. It is reflexive and transitive, but not antisymmetric. Consequently, Δ_ij is not a partially ordered set so that identities that are valid in U_ij, under some condition(s) expressed in terms of ≤, may not be valid in

. In particular, if a ≤ b, then a + b = b and a · b = a, and if a ≤ b and b ≤ a, then a = b are valid in U_ij, but not in

.

Algebra

, does better than D_ij when it comes to satisfying the minimum and the additional requirements above. The former holds if the differences are ignored, whereas the latter holds with no constraints.

Because it is possible to decide by using operations and the relation of

whether its two elements are decompositions of the same shape, the algebra sees decompositions as in Definition 2, that is as decompositions of shapes. This is handled by the following proposition.

Proposition 3. Let A and B be decompositions of shapes a and b, respectively, then a = b if and only if Σ_k=1,…,m′ A ≤′ Σ_k=1,…,n′ B and Σ_k=1,…,n B ≤′ Σ_k=1,…,m′ A, where m and n are cardinalities of A and B, respectively, and Σ′ is the extension of the sum +′ of

. █

Therefore, Σ_k=1,…,m′ A = A +′ A +′ A +′ … , where A appears m times on the right side of the equality. The proof then follows from the definition of ≤′ and the fact that a ∈ Σ_k=1,…,m′ A and b ∈ Σ_k=1,…,n′ B. The latter is due to the following lemma and its corollary.

Lemma 2. Let A = {x₁, x₂, … , x_n} be a decomposition, the sum S(k) = Σ_i=1,…,k′ A, where A appears k-times as an argument with k ≤ n, contains an element y = Σ_i=1,…,k x_i. Note that Σ′ is the extension of +′ of

whereas Σ is the extension of + of U_ij. █

The proof is based on the definition of +′ where each element of one decomposition is combined in sum + with each element of the other decomposition. Therefore, the lemma holds for k = 2 because S(2) = A +′ A contains shape x₁ + x₂. If we assume that it holds for k, 2 < k < n, so that S(k) contains shape z = Σ_i=1,…,k x_i, then it is easy to show that it also holds for k + 1. Sum S(k + 1) = S(k) +′ A contains shape z + x_k+1 = (Σ_i=1,…,k x_i) + x_k+1 = Σ_i=1,…,k+1 x_i, which completes the proof by the induction.

Corollary. Let A be as above and let a be the shape A analyzes, Σ S(n) then contains a. █

By Definition 2, a = Σ A = Σ_i=1,…,n x_i whereas by the lemma above, S(n) contains Σ_i=1,…,n x_i.

Note that the dual of Lemma 2 also holds, so that P(k) = Π_i=1,…,k′ A contains an element y = Π_i=1,…,k x_i, where Π′ is the extension of ·′ whereas Π is the extension of ·.

Computations involving sums and products satisfy the minimum requirement. For example, the decompositions in Figure 5a and b analyze shapes in Figure 3c and d. The latter are the respective sum and product of the shapes in Figure 5a and b, whereas the former are the respective sum and product of their decompositions in Figure 5f and g.

Unfortunately, the minimum requirement is not satisfied by computations involving difference. For example, decomposition in Figure 5c analyzes shapes in Figure 3a. The latter is not the difference of the shapes in Figure 5a and b, although the decomposition is the difference of their decompositions in Figure 5f and g.

Although

treats shapes as spatial objects, the same way U_ij does,

is still a poor choice for computing with analyzed shapes. It does not satisfy the minimum requirement and most of the important identities (properties) of U_ij.

However, as with D_ij, special kinds of decompositions form a subalgebra in

, which is capable of handling analyzed shapes in a meaningful way. The decompositions are singletons containing the shape they analyze and nothing else. Approximating a shape with itself does not add much to the shape description, so that an algebra of such decompositions should behave as a shape algebra. This is true due to the following result.

Proposition 4. Any identity r = s valid in U_ij is valid in

if a singleton from

is assigned to each individual variable occurring more than once in r or s. █

This proposition is valid for any algebra and its complex counterpart; however, the proof in its generality is left to mathematicians. We will only show that it holds for one of the identities defining the distributivity of U_ij. Let A, B, C ∈

. The identity A ·′ (B +′ C) = (A ·′ B) +′ (A ·′ C), defining distributivity of ·′ over +′, is not valid in

, because A occurs twice on the right-hand side. However, if A is a singleton {a}, the identity becomes {a} ·′ (B +′ C) = ({a} ·′ B) +′ ({a} ·′ C) (′). Elements of {a} ·′ (B +′ C) are, in accordance with definitions of the operations ·′ and +′, of the form a · (x + y), where x ∈ B and y ∈ C. In contrast, all of the elements of ({a} ·′ B) +′ ({a} ·′ C) are of the form (a · x) + (a · y). Because U_ij is distributive, a · (x + y) = (a · x) + (a · y), so that identity (′) holds.

The algebra for singleton decompositions can now be constructed as follows. The set A_ij ⊂ Δ_ij of singleton decompositions together with operations +′, ·′, and −′ forms the Boolean part of a new algebra A_ij. The group part and the operation of the group action of A_ij are the same as in

.

Proposition 5. The new algebra A_ij is a subalgebra of

isomorphic with U_ij. █

For

to hold A_ij should be closed under the operations of

. Indeed, according to definitions of these operations we have {a} +′ {b} = {a + b}, {a} ·′ {b} = {a · b}, and {a} −′ {b} = {a − b}, where a, b ∈ U_ij and {a}, {b} ∈ A_ij (′). In set theory, a singleton (decomposition) can uniquely be specified as {a} = {x| x = a}, whereas (shape) a can be “recovered” from the singleton (decomposition) via ∪{a} = a. Therefore, there is one to one correspondence between shapes and their singleton decompositions. This correspondence preserves operations of U_ij as evident in identities (′), which completes the proof.

3.3. Algebras of analyzed shapes

Even though

treats shapes as spatial entities, the only analyzed shapes it can meaningfully handle are (trivial) singleton decompositions. This is rather disappointing because analyzed shapes play an important role not only in design, but also in our everyday lives. However, there is still some room for improvement of

.

One can normalize operations of

to make a shape algebra homomorphic to it, the minimum requirement. The normalization relies on the concept of relativization of the structure of a shape to its subshape. In

, the relativization can be expressed in accordance with the following proposition.

Proposition 6. Let a be a shape,

its decomposition, and shape b its part. Set B = {b}·′ A is a decomposition of b, which is the relativization of A to b. █

Set B = {b} ·′ A = · ({b} × A) = {x · y| x ∈ {b}, y ∈ A} = {b · x| x ∈ A}, which is, according to Definition 3, the relativization of A to b.

If A is the result of a computation with decompositions and b is the result of the same computations carried on with the corresponding shapes, then B is the result of the normalized operation. If A is the result of a sum or a product, then B = A, which means that normalization does not affect these operations. The normalized sum +* and product ·* are the same as +′ and ·′. Normalization affects only the difference, which becomes A −* B = {Σ A − Σ B} ·′ (A −′B) = A −′ {Σ B}, where A and B are decompositions. Set A −* B is clearly a decomposition of the difference of shapes analyzed by decompositions A and B. It has the structure of A, but not of B.

It is now possible to define a new normalized complex algebra of decompositions

, which is the same as

except for the Boolean operations, which are now normalized.

For example, the decompositions in Figure 6a, b, and c are the respective sum, product, and difference of decompositions in Figure 3 when computed in the framework

. Note that sum in Figure 6a and product in Figure 6b are the same as the ones computed in the framework of

(Fig. 5a,b).

Computing in : (a) sum, (b) product, and (c) difference of decompositions in Figure 3.

The new algebra satisfies the minimum requirement: U_ij is homomorphic to it. However, the two algebras still have different properties.

These differences could be largely reduced if the ordering on decompositions is changed to reassemble that on shapes. Relation ≤′ is a preorder on Δ_ij, whereas ≤ is a partial order on U_ij. Universal algebra provides a procedure for turning a preordered set into a partially ordered one (Vickers, 1989). The partially ordered set can then be extended to an algebra to handle analyzed shapes.

The procedure starts with equivalence relation ≡ defined on Δ_ij in terms of preorder ≤′. Two decompositions A and B are equivalent with respect to ≡, or equivalent modulo ≡, or A ≡ B, if and only if A ≤′ B and B ≤′ A.

For example, decompositions in Figure 7a and b are equivalent modulo ≡. Every element of the former decomposition is a part of shape c from the latter decomposition. In contrast, the empty shape from the former decomposition is a part of every element of the latter decomposition. Consequently, the latter includes the former decomposition in accordance with the definition of ≤′. It is easy to verify that the relation also holds if the decompositions exchange places.

(a,b) Decompositions are equivalent modulo ≡. Every element of (a) is a part of (c) the shape included in (b). The empty shape in (a) is a part of every element of (b). Every element of (b) is a part of shape (c) included in (a). The empty shape in (b) is a part of every element of (a).

In the next step, Δ_ij is partitioned so that decompositions equivalent modulo ≡ are grouped into subsets or equivalence classes. Each decomposition A belongs to a class [A] _≡ and the set of all equivalence classes is a quotient set Δ_ij/≡.

Finally, set Δ_ij/≡ is partially ordered by ≤′ so that [A]_≡ ≤′ [B] _≡ if and only if A ≤′ B (Vickers, 1989).

Each equivalence class of Δ_ij/≡ contains decompositions that have the following common properties.

Proposition 7. Two decompositions are equivalent modulo ≡ if and only if they share the sets of minimal and maximal elements. █

Let min A and max A denote sets of minimal and maximal elements of a decomposition A, and let B be a decomposition. We will first prove the following lemma.

Lemma 3. If A ≡ B, then max A ⊆ B, max B ⊆ A, min A ⊆ B, and min B ⊆ A. █

Let x ∈ max A. According to the definition of ≡, A ≤′ B and, according to definition of ≤′, there is y ∈ B such that x ≤ y. According to the same definitions, B ≤′ A and there is z ∈ A such that y ≤ z. Consequently, x ≤ y ≤ z (*) and because x is a maximal element of A and z is an element of A, the two have to be equal for (*) to hold. This makes x equal to y so that x ∈ B, which proves that max A ⊆ B. The proof of max B ⊆ A follows from the symmetry of ≡. The proofs of the last two assertions may be done in the similar fashion to complete the proof of the lemma.

Let us now assume that max A = max B and min A = min B. For every x ∈ A there is y ∈ max A such that x ≤ y, and because max A = max B, y ∈ B. Similarly, for every v ∈ B there is u ∈ min B such that u ≤ v, and because min A = min B, u ∈ A. Consequently, A ≤′ B in accordance with the definition of ≤′. The proof of B ≤′ A may be obtained in the similar fashion so that A ≡ B, which completes the proof of the “if” part of the proposition.

Now assume that A ≡ B, but the two do not have a common set of maximal elements. For example, there is an element x maximal in A but not in B. According to Lemma 3, max A ⊆ B so that x ∈ B. Because x is not maximal in B there is y ∈ max B such that x < y. Again, according to lemma 3, max B ⊆ A so that y ∈ A, and because x is maximal in A, x < y does not hold. This refutes our assumption that max A ≠ max B so that max A = max B holds. The proof that min A = min B holds could be obtained in a similar fashion, which completes the proof of the “only if” part of the proposition.

Corollary 1. Decompositions equivalent modulo ≡ are analyzing the same shape. █

Let A and B be two decompositions such that A ≡ B. The shape that A analyzes is Σ A and because a + b = a if b ≤ a, we can take Σ max A for Σ A. By the same token, the shape that B analyzes or Σ B is the same as shape Σ max B. According to Proposition 7, max A = max B so that Σ A = Σ max A = Σ max B = Σ B, which completes the proof.

Corollary 2. There is a unique smallest representative max A ∪ min A for each equivalence class [A]_≡, where A is a decomposition. █

Note that the word smallest is related to the cardinality (number of elements) of decompositions.

For Δ_ij/≡ to be extended to a quotient algebra, equivalence ≡ needs to be a congruence on

.

Proposition 8. Equivalence relation ≡ is a congruence on

. █

Let

and let A ≡ B and C ≡ D. For ≡ to be a congruence, substitution property has to hold for each operation of

. Substitution property for the sum is A +* C ≡ B +* D. Elements of max(A +* C) are of the form x + y, where x ∈ max A and y ∈ max C. In contrast, elements of max(B +* D) are of the form u + v, where u ∈ max B and v ∈ max D. Because, max A = max B and max C = max D, in accordance with Proposition 7, max(A +* C) = max(B +* D). Similarly, min(A +* C) = min(B +* D), so that, according to Proposition 7, A +* C ≡ B +* D, which proves that the substitution property holds for +*. It can be shown that the same property also holds for ·* and −*, which renders ≡ a congruence on

.

It is now possible to construct a quotient algebra

, with elements that are classes of decompositions that share the shape they analyze and sets of minimal and maximal elements. The set of such classes is partially ordered with a smallest element, which is a one-element equivalence class of {0}, but with no greatest element.

Computations in

are carried on as in

. For example, computations in Figure 6 may be seen as computations in

, except that the decompositions are now seen as representatives of their equivalence classes. Consequently, any other representative of the same class may be used in the place of any of the decompositions. For example, decomposition in Figure 6a may be replaced with decomposition in Figure 8a because they belong to the same equivalence class. That is, they share sets of maximal and minimal elements, represented in Figure 8b and c, respectively.

(a) Decompositions and Figure 6a belong to the same equivalence class. (a,d) Decompositions both analyze (b) the shape, but they do not belong to the same equivalence class. Their sets of maximal and minimal elements are different: (b,c) for (a), and (c) and {0} for (d), respectively.

Although all decompositions of an equivalence class are guaranteed to analyze the same shape, there are other classes in

with decompositions that analyze that very shape.

For example, decompositions in Figure 8a and d both analyze the shape in Figure 8b, but they do not belong to the same equivalence class. The former decomposition has a singleton containing the shape (Fig. 8b) as the set of maximal elements and the decomposition in Figure 8c as the set of minimal elements. In contrast, the decomposition in Figure 8d has c as the set of maximal elements and a singleton containing an empty shape as the set of minimal elements.

There is no one to one correspondence between shapes of U_ij and classes of

so that the two algebras are not isomorphic. However, any subalgebra of

whose elements enumerate shapes in a one to one fashion is isomorphic with U_ij.

For example, the algebra A_ij of singleton decompositions can be constructed as a subalgebra of

. For each singleton {a}, sets of maximal and minimal elements are equal and both are equal to {a}. This places {a} into an equivalence class of

, with {a} the only element.

The following proposition sheds some light on the structure of decompositions that are building blocks of subalgebras of

that are isomorphic with U_ij.

Proposition 9. Only decompositions that contain the shape they analyze and have exactly one minimal element qualify as the members of equivalence classes forming a subalgebra of

isomorphic with U_ij. █

Members of the Boolean part of such a subalgebra are equivalence classes of decompositions, which according to Proposition 7, are characterized by the common sets of maximal and minimal elements. Proposition 9, however, requires these sets to be singletons. The following two lemmas prove this statement.

Lemma 4. No subset of

with elements that are classes of decompositions characterized by nonsingleton sets of maximal elements is a subalgebra of

isomorphic with U_ij. █

Let

be such a subset and let [A] _≡ be one of its elements, where A = {x₁, x₂, … x_n}, maxA = {x₁, x₂, … x_k}, 2 ≤ k ≤ n, and A analyzes shape a. If we take a finite sum Σ_i=1,…n* [A]_≡ = Σ_i=1,…n′ [A]_≡ = [Σ_i=1,…n′ A]_≡ = [S(n)]_≡ then, according to the corollary of Lemma 2, a is an element of S(n). Because U_ij is homomorphic to

, both S(n) and A are analyzing the same shape, a. Consequently, max S(n) = {a}, and because k ≥ 2 max A = {x₁, x₂, … x_k} ≠ max S(n) so that [A]_≡ ≠ [S(n)]_≡. This means that if [S(n)]_≡ is an element of V_ij and V_ij is a subalgebra

, then V_ij is not isomorphic with U_ij because shape a is represented by the two different elements: [A] _≡ and [S(n)]_≡ of V_ij. If [S(n)]_≡ is not an element of V_ij, then V_ij is not a subalgebra of

, which completes the proof.

Lemma 5. No subset of

with elements that are classes of decompositions characterized by nonsingleton sets of minimal elements is a subalgebra of

isomorphic with U_ij. █

The proof is similar to that of Lemma 4 except that P(n) = Π_i=1,…,n′ A and the dual of Lemma 2 are used in the place of S(n) and Lemma 2.

According to the lemmas above, only subsets of

with elements that are equivalence classes of decompositions characterized by singleton sets of minimal and maximal elements may be subalgebras of

isomorphic with U_ij. If max A is a singleton, it has to be equal to {a}; however, for min A we have more options. For example, in A_ij, min A is the same as max A, namely {a}.

Another example of a subalgebra of

isomorphic with U_ij is based on equivalence classes of decompositions that recognize the shape they analyze, as well as the fact that the empty shape is a part of any shape. It may contain other parts too, but has, at least, to recognize the two. Such a decomposition satisfies Proposition 9 with minimal element 0. For each shape a ∈ U_ij there is exactly one equivalence class [{a, 0}]_≡ of such decompositions that corresponds to a. Set C_ij ⊂ Δ_ij/≡ of such equivalence classes can be elevated to an algebra in accordance with the following result.

Proposition 10. Set C_ij together with operations +*, ·*, and −*, is the Boolean part of an algebra C_ij, which is a subalgebra

isomorphic with U_ij. █

Let a and b be shapes from U_ij, A and B their respective decompositions, and t a transformation from the group part of

. In addition, let A and B be members of some equivalence classes of C_ij.

Because [A]_≡ ∈ C_ij, {a, 0} ⊆ A so that max A = {a} and minA = {0}. According to Corollary 2 of Proposition 7, there is a unique representative of [A] _≡, such that [A] _≡ = [max A ∪ min A] _≡ = [{a, 0}]_≡. Consequently, there is only one equivalence class in C_ij containing decompositions of a, each class of C_ij corresponds to only one shape, and for every shape in U_ij there is a corresponding class in C_ij. The correspondence is a bijection, thus, enumerating all of the elements of U_ij and C_ij. It needs to be shown that the correspondence also preserves the operations and transformations of C_ij (or U_ij).

For the sum we have [A]_≡ +* [B]_≡ = [{a, 0}]_≡ +* [{b, 0}]_≡ = [{a + b, a, b, 0}]_≡ = [{a + b, 0}]_≡ ∈ C_ij in accordance with Corollary 2 of Proposition 7. The result of the sum of equivalence classes is the equivalence class of the sum of corresponding shapes. The same is true for products and differences: [A]_≡·*[B]_≡ = [{a, 0}]_≡ ·*[{b, 0}]_≡ = [{a · b, 0}]_≡ ∈ C_ij and [A]_≡ −* [B]_≡ = [{a, 0}]_≡ −* [{b, 0}]_≡ = [{a − b, 0}]_≡ ∈ C_ij. This renders C_ij a subalgebra of the Boolean part of

isomorphic with the Boolean part of U_ij.

Set C_ij is closed under transformations of

and the correspondence above preserves the transformations. We have t([A]_≡) = t([{a, 0}]_≡) = [{t(a), 0}]_≡ ∈ C_ij. Consequently, C_ij and U_ij are isomorphic, which completes the proof.

For example, each of the decompositions in Figure 3 may be augmented with an empty shape and used to compute in the framework of C_ij as illustrated in Figure 9.

Computing in Cij: (a) sum, (b) product, and (c) difference of decompositions in Figure 3, each augmented with an empty shape.

Algebra C_ij is the most interesting of the algebras constructed here. It computes with decompositions that are nontrivial shape approximations and behaves like a shape algebra. The shape approximations of C_ij are rather general ones. They may contain any set of parts of a shape provided that the shape itself and the empty shape are included. This renders C_ij an excellent choice as a framework for computations with decompositions seen as shape approximations. Computations carried on with shapes in the framework of U_ij algebra can now be repeated with analyzed shapes in the framework of C_ij algebra.

For example, the result [{a + b, a, b, 0}]_≡ of the sum above seems like a reasonable explanation of the sum of shapes a and b. One should expect both a and b to be preserved by the sum. If we add two new parts c ≤ a and d ≤ b to the decompositions above, the same computation becomes the following:

The new parts are preserved, whereas their sum c + d, also included, extends the computation to the new parts. The two principles, preservation and extension, inform computations in C_ij. A computation preserves as much as possible of the original parts, but also extends (to) these parts.

It has been believed that algebras A_ij and C_ij are the only subalgebras of

isomorphic with U_ij (Krstic, 2004); however, Proposition 9 seems to allow for construction of some other such algebras. This is based on the fact that for a given shape a we can create an equivalence class [{a, f (a)}]_≡ to represent a. Operator f (on the Boolean part of U_ij) has to be chosen so that f (a) is a part of a. For a set of such equivalence classes to be an algebra isomorphic with U_ij, operator f has to satisfy the following five conditions:

where a and b are shapes from the Boolean part of U_ij and t is a transformation from the group part of U_ij.

Because every shape is guaranteed to be a part of itself and to have 0 as a part we can take operator f to be an identity f (a) = a or a constant f (a) = 0 and get algebras A_ij and C_ij, respectively. In both cases, f satisfies all five of the conditions above. We may also try some other ways of defining f.

For example, we can pick parts of a by using some fixed shape c so that f (a) = a · c, or alternatively f (a) = a − c. In both cases, f satisfies first four of the above conditions, rendering the related sets of equivalence classes, algebras isomorphic, with the Boolean part of U_ij. However, f fails the fifth condition, and the related sets are not closed under transformations of the group part of U_ij.

To satisfy the fifth condition we may choose f so that it involves transformations. For example, f (a) = a · τ(a), or alternatively f (a) = a − τ(a), where τ is a transformation defined in a coordinate system local to a. When a is transformed, so is its local coordinate system. If a is represented by an equivalence class [{a, a · τ(a)}]_≡, then t(a) is represented by [{t(a), t(a) · t ○ τ ○ t⁻¹(t(a))}]_≡ = [{t(a), t(a) · t ○ τ(a)}]_≡, where ○ is a group composition. Alternatively, if a is represented by [{a, a − τ(a)}]_≡, then t(a) is represented by [{t(a), t(a) − t ○ τ(a)}]_≡. Although f satisfies the first and fifth condition, it fails the second and the third one. We may choose for τ to be defined in a global coordinate system. Thus, if a is represented by [{a, a · τ(a)}]_≡, or by [{a, a − τ(a)}]_≡, then t(a) is represented by [{t(a), t(a) · τ(t(a))}]_≡ = [{t(a), t(a) · τ ○ t(a)}]_≡ or [{t(a), t(a) − τ ○ t(a)}]_≡, respectively. This again satisfies the first four conditions but fails the last one because τ ○ t(a) may differ from t ○ τ(a).

Although all of the possibilities for f have not been exhausted, we may speculate with a great certainty that f (a) = a and f (a) = 0 are the only solutions that satisfy all of the conditions above. Thus, we have the following conjecture.

Conjecture 1. Algebras A_ij and C_ij, which are subalgebras of

isomorphic with U_ij, are the only such subalgebras. █

Conjecture 1 singles out both: algebra C_ij, as the only nontrivial algebra for analyzed shapes, and also decompositions that recognize the shape they analyze as well as the empty shape as the only meaningful shape approximations.

3.4. Properties of decompositions

Thus far, different algebras of decompositions were constructed and analyzed. Now, attention will be shifted to different decompositions of shapes emerging with these algebras. Seven algebras D_ij,

, have been defined. The first four compute with general/unstructured decompositions, whereas the remaining three use different kinds of structured decompositions.

The structure of decompositions unfolds on two levels: local, exposing the relations between the elements of a decomposition; and global, relating these elements to the parts of the shape analyzed by the decomposition. If a decomposition is to be an approximation of a shape, then its structure on the global level is of the most importance. All parts of the shape should be represented by the elements of the decomposition. There are infinitely many shape parts, but only finitely many elements so that the relation between the two is many to one.

For a given shape a, its part x, and its decomposition A, this relation is as follows. There may exist two elements y and z in A such that y is a part of x and x is a part of z, or y ≤ x ≤ z. Decomposition A approximates part x by means of elements y and z. If y exists, then x is bottomed by y, or x has at least properties of y. If z exists, then x is topped by z, or x has at most properties of z. If both elements exist, then x is bounded by y and z, or x has at least properties of y and at most properties of z. If neither y nor z exist, then x is not recognized by decomposition A. All elements of A, when seen as parts of a, are bounded by themselves.

Algebra A_ij works with singleton decompositions that are singleton sets of Δ_ij. These contain only the shape they decompose and nothing else. Each part of the shape is trivially represented, topped, by the shape itself (i.e., it has at most properties of the shape).

In set algebras, where shape parts are of the most importance, singletons inform that the shape is a part of itself. Singletons are less informative in complex algebras. The former depend on shape structures, but singletons by themselves do not structure shapes. Singletons and their algebras simply demonstrate that complex algebras behave well in a boundary case. They do so by validating all of the identities of U_ij, as shown in Proposition 4.

Algebra

uses discrete decompositions, or subsets of a finite set K_ij of pairwise discrete shapes. No two elements of such a decomposition have common parts. Approximating shapes with discrete decompositions is thrifty, with no redundancy or ambiguity. The only shape parts that are bounded are the elements of a decomposition. All other parts are topped by only one element, bottomed by one and possibly more elements, or not recognized at all. Any part of the shape that consists of proper parts of two or more elements of the decomposition is not recognized.

The set in Figure 10a is an example of a discrete decomposition of the shape in Figure 3a, whereas the shapes in Figure 10b, c, and d are its proper parts. The shape in Figure 10b is topped by the first element of decomposition a, shape c is bottomed by both the second and the third element of decomposition a, whereas shape d is not recognized by a.

(a) A discrete decomposition of the shape in Figure 3a, with shape parts that are (b) topped, (c) bottomed, or (d) not recognized by decomposition (a).

Discrete decompositions are good representations of finished designs ready to be assembled from the parts that are elements of the decompositions.

By including the sums of the original elements, a discrete decomposition could extend to a hierarchical structure. Hierarchies are often used in design and elsewhere because their straightforward structure shows not only the parts of a shape, but also the way the parts are put together to assemble the shape.

The algebra of analyzed shapes C_ij computes with bounded decompositions, which are, as shown earlier, the only meaningful shape approximations. These recognize the shape they analyze and the empty shape and can include other shape parts besides the two. At a minimum, no other parts are included. Every shape part is guaranteed to be bounded (represented) by such a decomposition. However, at a minimum, this representation is a rather trivial one. At most, a part has properties of the shape itself, and at least, no properties at all. The other elements a bounded decomposition may contain contribute to a finer shape part representation. Shapes in Figure 5b and c are examples of bounded decompositions.

The two shapes recognized in a minimum bounded decomposition are important from the algebraic point of view. They work in computations to preserve structures and shape parts recognized by decompositions.

For example, if two shapes a and b are analyzed by their respective bounded decompositions A and B and if the product A ·* B is taken, then shape a from A combines with elements of B to preserve the structure recognized by B, whereas shape b from B combines with the elements of A to preserve the structure recognized by A. If b ≤ a, then a preserves elements of B as well. Similarly, b preserves elements of A if b ≤ a. The empty shape has the same function in sums: the one in A preserves elements of B and vice versa. Both a and b assure that the product, sum, or difference of A and B contains the shape it analyzes: a + b, a · b, or a − b, respectively.

Bounded decomposition may serve as the basis for creating more structured decompositions of shapes. They may satisfy additional conditions to become lattices, topologies, groups, and Boolean algebras.