1. INTRODUCTION
Shapes are part of our everyday experience and play important roles in
many human activities. Shapes come without apparent structure, therefore
rendering any division into parts possible. However, any attempt to
(verbally) describe a shape inevitably leads to structuring the shape in
terms of its certain parts or to a shape decomposition. According
to Stiny (1991), “These are defined in a
variety of ways, but most simply as sets of shapes that show how their
sums are divided into parts of certain kinds.”
For example, the 3-dimensional shape in Figure
1a may be described as a table having four legs
and a board, which leads to the decomposition (Fig. 1b).
Decomposition of a table: (a) the original shape and (b) its
decomposition.
The fact that we can name things around us structures our surroundings
in a shape decomposition; whereas the simple naming of a shape structures
it by recognizing the shape as being a part of itself.
For example, the original shape in Figure 1a
is called a table in the description above. It should also be
included in the decomposition so that all of the shapes in Figure 1 become elements of the latter.
Shapes are rarely perceived in their natural form as
raw/unanalyzed, but rather approximated by their decompositions. An
unknown shape may at first appear as raw/unanalyzed, but it gradually
acquires a structure as one tries to understand it. As our understanding
grows, we move from raw/unanalyzed shapes to structured/decomposed
shapes.
Although important in many human activities, shapes are prime to
design and fine arts. Designers use shapes to specify things to make: to
provide information on how things function or how they should be built. To
do so, designers differentiate some parts of their designs by naming and
relating the parts. Shapes in designs are utilitarian in nature. They come
structured in decompositions with ambiguities removed in order to avoid
misunderstanding.
Ambiguities, although dismissed in designs, may well be at home in
fine arts. Shapes of art may serve a different purpose than those of
design. They need not be rationally understood. An art object may appear
pure, unanalyzed, and open to any kind of interpretation by both the
public and critics. This kind of ambiguity allows for multiple
interpretations and adds to the richness of the object.
Although the outcomes of a designer's or artist's efforts
may be different in nature (analyzed vs. raw shape), the design process
may well be the same.
In the course of design, an unanalyzed shape may be seen in a certain
way and accordingly decomposed into a certain set of parts. These may then
be used to compose new shapes. The latter may again be seen as unanalyzed,
only to be decomposed in some new way leading to new sets of parts. The
process may be repeated until a design or an art object is created. Moving
from analyzed to raw shapes creates an opportunity to see things in a
different way, which then moves shapes back from raw to analyzed. The
creative phases of the design process are characterized by shifts between
raw/unanalyzed shapes and decomposed/analyzed ones. Stiny's
(1994, 2001) shape
computations with unexpected outcomes are good examples of such shifts at
work.
Decompositions are used to describe shapes. They often appear in place
of shapes functioning as their approximations. The purpose of this paper
is to investigate how good such approximations are.
The investigation is conducted in the context of formal design theory
that involves shape grammars and related shape algebras. Central to the
theory are shape computations that attempt to formalize what designers do
when they design. To use decompositions as shape approximations, tools for
computing with decompositions are developed. In particular, algebras for
decompositions similar to algebras for shapes are introduced; and the
properties of such algebras are investigated and compared to the
properties of shape algebras. The measure of their agreement determines
how computations with decomposition may compare to the similar
computations with shapes. This ultimately shows how well shapes are
approximated by their decompositions.
1.1. A note on notation
Symbols like
are used in their standard set-theory meaning: empty set, intersection,
union, subset, proper subset, element of, not an element of, and power
set, respectively. Some standard set-theory notions are assumed, such as
the ordered set with related maximal and minimal elements, bounds, and
closures, as well as the direct product and related functions and
relations.
Computations are carried out in different algebras, where an
algebra is seen as a set of objects that is closed under a set of
operations. The elements of an algebra may satisfy certain equations, like
distributive or associative laws, which are axioms of that
algebra. Axioms may serve to distinguish classes of algebras such as
rings, lattices, groups, Boolean algebras, and so forth.
New algebras, in particular subalgebras and quotient algebras, are
constructed from the old ones. The former are subsets of an algebra that
are algebras themselves. The latter are algebras whose elements are
equivalence classes of some algebra, which has been partitioned with
respect to an equivalence relation of a certain kind: congruence.
Congruence preserves the operations of the algebra so that the result of
computations carried on with the equivalence classes of some elements of
the algebra is the equivalence class of the result of the same computation
carried on with the elements themselves.
Algebras with the same kinds of operations could be related via
certain mappings. If there is a mapping from an algebra to another algebra
such that the mapping enumerates all of the elements of the latter
algebra, and if it also preserves the operations of the algebras, then the
latter algebra is homomorphic to the former one. If the mapping
is also one to one, then the two algebras are isomorphic. A
mapping defining isomorphism is a surjection because it
enumerates all of the elements of the latter algebra and it is an
injection because it is one to one; thus, it is a
bijection.
We also make use of shape algebras (Stiny, 1991, 1992, 2001). These compute with shapes in a Boolean fashion
and are also closed under geometric transformations that act on shapes.
Shape algebras are seen as two-sorted (operating on objects of two
different sorts), conveniently keeping both shapes and transformations in
a single algebraic structure (Krstic, 1996,
1999, 2001). Shape
algebra (Uij) computes with
i-dimensional shapes occupying j-dimensional space
forming the set Uij (i,
j = 0, 1, 2, 3, and i ≤ j) and
j-dimensional geometric transformations forming the set
Tj.
The set of shapes Uij has a
lower bound, which is the empty shape denoted by 0, but has no upper
bound. Shapes from Uij, together
with Boolean operations of sum (+), product (·), and difference
(−), form a generalized Boolean algebra: a relatively
complemented distributive lattice with a smallest element (Birkhoff, 1993). This establishes the Boolean
part of Uij.
Transformations of Tj form a group
establishing the group part of
Uij. Transformations are combined
with the aid of group operations and act on shapes of
Uij by a binary operation of group
action that takes a shape a and a transformation t to
produce a transformed shape t(a).
Shape algebras could be extended to other design-related objects such
as labeled shapes, weighted shapes, or n-tuples of shapes. Such
algebras still have the shape algebra structure, but the objects they
operate on are not shapes.
1.2. Definition
Decompositions are used as shape descriptions that emphasize certain
properties of shapes. There are different ways to define a decomposition
of a shape depending mainly on the kind of information that is to be
highlighted.
For example, decompositions defined as directed graphs containing
shapes and spatial relations among them expose the details of how shapes
are generated with a shape grammar (Knight,
1988).
Decompositions defined simply as sets of shapes will be used
exclusively in this work. Although very elementary, the definition is
general. Such decompositions do only the minimum of what decompositions
should do: they structure unanalyzed shapes in terms of their certain
parts and nothing else. That is, certain properties (parts) of a shape are
chosen to represent the shape while others are neglected. This renders
decompositions: shape approximations that suit certain purposes.
Shape parts are central to decompositions, and any shape, with the
exception of shapes consisting of points, has infinitely many parts. A
picture is literally worth infinitely many words. The set of all
parts of a shape is the upper bound for all decompositions of that shape.
This set has some interesting properties that reveal shape structure.
Let B(a) denote the set that includes all of the
parts of a shape a. Any Boolean combination of parts of
a carried out in the algebra in which a is defined yield
another part of a. Set B(a) is a subalgebra of
this algebra closed under its Boolean operations. If a is a shape
from Uij, then
B(a) is a Boolean algebra (Stiny,
1980; Earl, 1997). Because a is
not changed by the transformations of its symmetry group
S(a), the set B(a) is closed under
S(a) in accordance with the following proposition.
Proposition 1. Set B(a) is closed under
the symmetry group of a, or S(a).
█
The proof follows from the definition of the symmetry group of a shape
and the order preserving nature of transformations. That is, if t
∈ S(a), than t(a) = a,
and if x ≤ a, then t(x) ≤
t(a). Consequently, t(x) ≤
a so that t(x) ∈
B(a).
This motivates the following definition: the maximal structure of
a shape a denoted by B(a) is
a two-sorted shape algebra with B(a) as the Boolean part
and S(a) as the group part.
The maximal structure of a is clearly a proper subalgebra of
Uij, which shows that shapes, like
their algebras, have a dual nature. They have parts that are shapes from
Uij closed under transformations
from Tj, where B(a) and
S(a) are respective upper bounds. The interplay of
structure and symmetry, which is central to design, emerges here in the
very nature of the building blocks of designs: shapes.
Although it is possible to have decompositions containing infinitely
many parts of a shape, like B(a), only finite
decompositions will be examined in this work. The former may be appealing
to mathematicians, but the latter are central to the design practice.
Definition 1. A finite nonempty set of shapes is a
decomposition. █
The set of all decompositions denoted by Δij
is a proper subset of
.
Set Δij is clearly without an upper bound when
ordered by ⊆. It also lacks a lower bound, because the empty set is
not a decomposition.
Definition 2. Let a be a shape, the set A
is a decomposition of a whenever it is a decomposition
and the sum of its elements is a, or a = Σ
A. █
Any decomposition is a decomposition of a shape because finite sums of
shapes are guaranteed to be shapes.
The set of finite subsets of B(a) that sum to
a is the set of all decompositions of a. Like
Δij, this set does not have an upper or a lower
bound and is closed under the symmetry group of a.
Decompositions structure shapes, and also structure their parts. In
Figure 2a, the square is structured as a
consequence of the structure of the double square in Figure 2b that contains it. Note that the location of
the shapes in some coordinate system is indicated by cross marks.
(a,b) Decompositions: the structure of (b) is recognized in (a)
whereas its elements are not.
The structure of an analyzed shape can be relativized to each of its
parts in accordance with the following definition.
Definition 3. If a is a shape, A its
decomposition, and shape b a part of a, then b
is implicitly structured in decomposition B = {b
· x| x ∈ A}, which is the
relativization of the structure of a to b or
the relativization of A to b. █
3. DECOMPOSITIONS AS SHAPE
APPROXIMATIONS
Shape grammars and later shape algebras have a history of more than
three decades as formal design theory tools. They have been established as
formalizations of design practice. The algebras model what designers do
when they draw and erase shapes, build, and modify models, or just move
shapes around to produce new spatial relations. Grammars and algebras are
capable of handling the emergence and ambiguity of shapes, which are
important in the most creative, exploratory phase of a design process
(Knight, 2003a, 2003b). In contrast, algebras of
decompositions operate on sets of shapes, but these may or may not be seen
as approximations of shapes. If decompositions are seen as shape
approximations, the properties of their algebras should match those of
shape algebras as closely as possible.
At minimum, an algebra for decompositions should be such that an
appropriate shape algebra is homomorphic to it. This guaranties that the
result of a computation carried on with decompositions of shapes is a
decomposition of the result of the same computation carried on with the
shapes themselves. Such symmetry between the two algebras is important if
shapes in computations are to be approximated by their decompositions.
Note that the mapping defining the homomorphism is the summation from
Definition 2.
At maximum, algebras for shapes and decompositions should be
isomorphic. At this point, symmetry between the algebras is complete and
decompositions behave as shapes. Such an algebra of decompositions becomes
a true algebra of analyzed shapes.
As an additional requirement, an algebra of decompositions should have
enough power to inform the decision on whether two of its elements are
analyzing the same shape. This renders the transition from an analyzed
shape to the raw unanalyzed shape possible within the framework of the
algebra.
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
Dij, 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 Dij an unlikely
choice if computations with analyzed shapes are an objective. However,
Dij 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
Dij, which is isomorphic with a
certain subalgebra of Uij.
Let Kij 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 Kij are pairwise
discrete shapes, combining them in products and differences yields no new
shapes except for the empty shape. For example, if a, b
∈ Kij 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
Kij. 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 Kij 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
Dij, and shape operations of
Uij, 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 Uij
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
Uij 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
Uij, 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
Uij, 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
Uij, but not in
.
Algebra
,
does better than Dij 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 = {x1,
x2, … ,
xn} 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
xi. Note that Σ′ is
the extension of +′ of
whereas Σ is the extension of + of
Uij. █
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
x1 + x2. If we assume that it
holds for k, 2 < k < n, so that
S(k) contains shape z =
Σi=1,…,k
xi, then it is easy to show that it also
holds for k + 1. Sum S(k + 1) =
S(k) +′ A contains shape z +
xk+1 =
(Σi=1,…,k
xi) +
xk+1 =
Σi=1,…,k+1
xi, 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
xi whereas by the lemma above,
S(n) contains
Σi=1,…,n
xi.
Note that the dual of Lemma 2 also holds, so that
P(k) =
Πi=1,…,k′ A
contains an element y =
Πi=1,…,k
xi, 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
Uij 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 Uij.
However, as with Dij, 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
Uij 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 Uij. 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
Uij 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 Aij ⊂
Δij of singleton decompositions together with
operations +′, ·′, and −′ forms the Boolean
part of a new algebra Aij. The group
part and the operation of the group action of
Aij are the same as in
.
Proposition 5. The new algebra
Aij is a subalgebra of
isomorphic with Uij.
█
For
to hold Aij 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 ∈
Uij and {a}, {b} ∈
Aij (′). 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
Uij 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:
Uij 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 Uij. 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
Uij 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 Uij.
For example, the algebra Aij 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 Uij.
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 Uij.
█
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 Uij.
█
Let
be such a subset and let [A] ≡ be one
of its elements, where A = {x1,
x2, … xn},
maxA = {x1, x2, …
xk}, 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 Uij
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 = {x1,
x2, … xk} ≠ max
S(n) so that [A]≡
≠ [S(n)]≡. This means that
if [S(n)]≡ is an element of
Vij and Vij is a
subalgebra
,
then Vij is not isomorphic with
Uij because shape a is
represented by the two different elements: [A]
≡ and
[S(n)]≡ of
Vij. If
[S(n)]≡ is not an element of
Vij, then Vij 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 Uij.
█
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 Uij. If max
A is a singleton, it has to be equal to {a}; however,
for min A we have more options. For example, in
Aij, min A is the same as
max A, namely {a}.
Another example of a subalgebra of
isomorphic with Uij 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 ∈ Uij
there is exactly one equivalence class [{a,
0}]≡ of such decompositions that corresponds to
a. Set Cij ⊂
Δij/≡ of such equivalence classes can be
elevated to an algebra in accordance with the following result.
Proposition 10. Set Cij
together with operations +*, ·*, and
−*, is the Boolean part of an algebra
Cij, which is a subalgebra
isomorphic with Uij.
█
Let a and b be shapes from
Uij, 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 Cij.
Because [A]≡ ∈
Cij, {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 Cij containing decompositions of
a, each class of Cij corresponds to
only one shape, and for every shape in Uij
there is a corresponding class in Cij. The
correspondence is a bijection, thus, enumerating all of the elements of
Uij and Cij. It
needs to be shown that the correspondence also preserves the operations
and transformations of Cij (or
Uij).
For the sum we have [A]≡ +*
[B]≡ = [{a,
0}]≡ +* [{b,
0}]≡ = [{a + b, a,
b, 0}]≡ = [{a + b,
0}]≡ ∈ Cij 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}]≡ ∈
Cij and
[A]≡ −*
[B]≡ = [{a,
0}]≡ −* [{b,
0}]≡ = [{a − b,
0}]≡ ∈ Cij. This
renders Cij a subalgebra of the
Boolean part of
isomorphic with the Boolean part of
Uij.
Set Cij is closed under transformations
of
and the correspondence above preserves the transformations. We have
t([A]≡) =
t([{a, 0}]≡) =
[{t(a), 0}]≡ ∈
Cij. Consequently,
Cij and
Uij 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 Cij 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 Cij 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
Cij 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
Cij an excellent choice as a
framework for computations with decompositions seen as shape
approximations. Computations carried on with shapes in the framework of
Uij algebra can now be repeated with
analyzed shapes in the framework of
Cij 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
Cij. A computation preserves as much
as possible of the original parts, but also extends (to) these parts.
It has been believed that algebras
Aij and
Cij are the only subalgebras of
isomorphic with Uij (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
Uij) 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
Uij, operator f has to
satisfy the following five conditions:
where a and b are shapes from the Boolean part of
Uij and t is a
transformation from the group part of
Uij.
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 Aij and
Cij, 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
Uij. However, f fails the
fifth condition, and the related sets are not closed under transformations
of the group part of Uij.
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−1(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
Aij and
Cij, which are subalgebras
of
isomorphic with Uij,
are the only such subalgebras. █
Conjecture 1 singles out both: algebra
Cij, 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
Dij,
,
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 Aij 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
Uij, as shown in Proposition 4.
Algebra
uses discrete decompositions, or subsets of a finite set
Kij 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
Cij 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.
4. DISCUSSION
If algebras for shapes are good models of how shapes are used in
design, then algebras of decompositions may inform on how analyzed shapes
are utilized. Table 1 sorts all of the algebras
for decompositions constructed here and highlights the ones suitable for
computing with analyzed shapes. It also exposes relationships among the
algebras and shows how they relate to shape algebras.
Algebras for decompositions
Unstructured decompositions are not suitable as approximations of
shapes. Neither set nor complex algebras of general decompositions could
be used to duplicate computations with shapes. This could only be achieved
with decompositions structured in some ways. Two such structures were
distinguished: discrete decompositions and bounded decompositions.
The structure of a discrete decomposition is minimum in the sense that
there is no overlap between the elements. The same amount of material
would be used for making all of the elements of a discrete decomposition
as for making the shape itself.
However, bounded decompositions are far from being minimum because
they always contain the shape they analyze and may contain some other
parts as well. Although their structure comes from purely algebraic
considerations, it is not without intuitive appeal. The presence of both,
the shape analyzed by a decomposition and the empty shape, provides
certain context for the other shape parts recognized by the
decomposition.
The former shape assures that the parts are always seen in the context
of the whole. This local context is given explicitly by the fact that the
whole is a member of the decomposition. If a description is associated
with a bounded decomposition, it contains the name of the shape analyzed
by the decomposition. In this sense, bounded decompositions are
named.
The empty shape in a bounded decomposition implies the global context
in which the analyzed shape is placed. It shifts attention from shape
parts to the shape surroundings, which are implied by the absence of the
parts. In an associated description, the empty shape may map to a
description of the shape surroundings.
Algebra Cij suggests that both
local and global contexts are necessary for decompositions to be
successfully used as shape approximations. How intuitive is this? Do we
analyze (see) shapes with their parts always related to both the whole and
its surroundings? These questions are interesting in their own right, but
need to be decided by cognitive psychologists.
For our part, future research should concentrate on moving from
general decompositions to ones tailored to specific applications. This may
lead to decompositions with more elaborate structures.
As mentioned earlier, both discrete and bounded decompositions could
be extended to more structured entities. The elements of such
decompositions may form different algebras. The latter could then be
combined within the framework of algebras capable of preserving the
algebraic structure of decompositions.
For example, Stiny (1994, 2001) computes with decompositions that are topologies
and Boolean algebras, whereas Krstic (1996) does
it with decompositions that are lattices, hierarchies, topologies, Boolean
algebras, and Boolean algebras with operators. Such decompositions are
able to handle a variety of problems, from continuity of computations in
shape grammars, to recasting spatial computations with shapes into
nonspatial ones with symbols.
4.1. A note on implementation
Although this work is theoretical, the results obtained could lead to
practical applications. It would be advantageous to be able to experiment
with shape decompositions used as shape approximations, or analyzed
shapes. This way the assumptions we make about shapes and their parts will
be included in computations with shapes and affect the results of such
computations.
Major domains of implementation for shape algebras are shape grammars
(production systems), which use rewriting rules to generate designs.
Grammars were introduced over three decades ago by George Stiny and James
Gips, and were successfully used to generate new design styles and analyze
the existing styles (Stiny, 2001). Computer
implementations of shape grammars are many, ranging from general grammar
interpreters (Krishnamurti, 1982; Krishnamurti, & Giraud, 1986; Chase, 1989; Piazzalunga &
Fitzhorn, 1998; Tapia, 1999) to ones
specific to certain design styles (Flemming,
1987; Agrawal & Cagan, 1998).
Algebras developed here should serve as a framework for a new kind of
grammars for analyzed shapes (shape decompositions), thus extending the
shape grammar formalism. Computer implementations of such grammars could
be based on the existing shape grammar interpreters because operations of
algebras
are extensions of shape operations (+, ·, and −) to direct
products of decompositions. Such an operation can be computed by computing
a number of shape operations.
For example, to compute the sum or product of decompositions
A and B in
,
we need to compute cardAcardB corresponding shape
operations, where cardA and cardB are cardinalities of
the respective decompositions. The same number of shape operations is
needed to compute a difference in
.
However, for difference A − B in
,
only cardA shape operations is needed if the shape B
analyzes is known. If this shape is not known, another cardB
operations is needed to compute Σ B, which amounts to total
of cardA + cardB operations for the difference. To
transform a decomposition A we need cardA shape
transformations. In
,
the number of shape operations needed to compute a single analyzed shape
operation could be further reduced if the unique smallest representatives
for equivalence classes are used (Corollary 2 of Proposition 7), which for
Cij will amount to just one shape
operation. This is not surprising because
Cij and
Uij are isomorphic. However, by
using the smallest representatives in
Cij, all of the distinguished shape
parts that are not included in the representatives are lost in
computations. Therefore, there is no advantage in computing with
decompositions instead of shapes themselves. Even without using the
smallest representatives, computations could be reduced because bounded
decompositions of Cij are guaranteed
to contain empty shape so that shape operations involving it may be
omitted. For the sum or product of decompositions A and
B in Cij we need
(cardA − 1)(cardB − 1) shape operations; and
for the difference A − B or transformation
t(A), cardA − 1 shape operations. Note
that in the case of difference above there is no need to compute Σ
B because it is already an element of B, and one only
needs to keep track of it. The latter task is not difficult because of
isomorphism between Cij and
Uij. If one knows Σ A
and Σ B, then computing Σ(A + B) is
simple because it is equal to Σ A + Σ B. The
same is true for products and differences, Σ(A ·
B) = Σ A · Σ B and
Σ(A − B) = Σ A − Σ
B.
A shape generation with a shape grammar starts with an initial shape,
which is then gradually changed by recursive applications of shape rules.
Similarly, an analyzed shape generation should start with an initial
analyzed shape (shape decomposition). To change an analyzed shape
C with a shape rule A → B, which replaces
an analyzed shape A with an analyzed shape B, one needs
a transformation t under which A becomes a part of
C, or t(A) ≤′ C. If such
t exists, then a transformed analyzed shape
t(A) is removed from C and replaced with the
transformed analyzed shape t(B) to create a new analyzed
shape C′. This can be accomplished by computing four
operations from an algebra for analyzed shapes, in accordance with the
following expression.
To implement the expression above in
Cij, one needs to compute
cardA − 1 of shape operations for t(A),
cardB − 1 for t(B), cardC
− 1 for C − t(A) and another
(cardC − 1) (cardB − 1) for the sum, which
totals cardBcardC + cardA − 2 of shape
operations. This is k = 1/4 (cardBcardC +
cardA − 2) times more shape operations per rule application
than is needed in standard shape grammars. Note that k = 1 if
decompositions in the computations are of cardinality 2, which means at
they are the smallest representatives. This is expected because
Cij and
Uij are isomorphic. If we take
n for an average number of elements for decompositions in
computations, then k = (n/2)2 is an
approximation with less then 2% error for n > 50. Computation
time is proportional to the square of cardinalities of decompositions in
computations. The time could be reduced with the aid of parallel
computing. Operations in Cij are
extensions of shape operations to direct products of decompositions and
are done componentwise, which may be computed in parallel.
Subshape evaluations necessary to determine transformation t
are computationally the most complex operations a shape grammar
interpreter faces. However, no complexity is added for evaluating
decompositions of Cij. Because
Cij and
Uij are isomorphic,
t(A) ≤′ C if and only if
t(Σ A) ≤ Σ C so that shapes Σ
A and Σ C could be evaluated instead of their
decompositions A and C.
We have not elaborated on implementations of algebras
as there are no computational issues with these algebras. Decompositions
of the first algebra are, for any practical application, shapes themselves
whereas operations of the last two algebras are set operations, which are
easier to implement than standard shape operations.
