Kotsopoulos S, Ph.D. Dissertation, Massachusetts Institute of Technology, 2005
II. Shape Computation Theory
1. Introduction
2. Computational Theory
3. Computational Design Theory
4. Shape Computation
4.1. SHAPE CALCULUS A B C
In the previous examples two shapes a and b produce some new shape c.
It is expected that shapes made out of lines, planes and solids fuse or exchange parts without preconditions.
Normally, shapes made out of lines produce other shapes made out of lines. Shapes made out of planes produce
other shapes made out of planes. And, shapes madeout of solids, produce other shapes made out of solids.
The “part of” relation < is a formal relation, which succeeds to express our spatial intuition that spatial elements of
dimension greater than zero, namely lines, planes or solids, can be embedded on one another. Intuitively,
when all the parts of a shape a made out of lines are embedded on another shape b also made out of lines, the
first shape becomes part of the second. Therefore, we can write a < b.
The relation < is an order relation and renders the sets Uij of shapes, into relatively complemented lattices.
The relation < is:
reflexive, because every shape a, made out of points, lines, or planes is part of itself a < a
antisymmetric, because for any two shapes a, b if shape a is part of shape b, (a < b) and
shape b is part of shape a, (b < a), then a = b
transitive, because for any three shapes a, b, c if a < b and b < c, then a < c.
Further, each Uij lattice is distributive, because any three shapes a, b, c satisfy the identities:
(a • b) + (b • c) + (c • a) = (a + b) • (b + c) • (c + a)
a • (b + c) = (a • b) + (a • c)
a + (b • c) = (a + b) • (b + c)
where the shape operations • and + substitute the lattice operations of join and meet.
For any two shapes a, b in the algebras Uij there is a least element denoted by the empty shape. But, in all
algebras, except from U00, there is no upper element. Because there is no shape containing all shapes.
Although there is no upper element for shapes, complements are defined in relative manner.
Therefore, each Uij lattice is a relatively complemented one.
For any three shapes a, b, c belonging to some algebra Uij such that a < b < c a shape b' exists such that
b • b' = a, and b • b' = c. The shape b' is denoted as the relative complement of b within [a, c]. And because the
lattice is distributive, all relative complements are uniquely determined in it. That is, if a < b < c at most one b'
exists satisfying both b • b' = a, and b • b' = c.
The lattice-theoretic operations of join, meet and complement substituted with the operations of sum (+),
product (•), and complement ( ' ), form a Boolean algebra. The algebra U00 containing a single point is an
example.
The sextuple ( U00, +, •, ', 1, 0 ) forms a Boolean algebra with two binary operations +, •, and a unary operation
of complementation ', together with two special elements: the zero 0, and the unit 1, which are not equal. The
commutative and distributive laws hold for the single point x, which belongs to the algebra U00.
Also, it holds that
x + 0 = x
x + x' = 1
x • 1 = x
x • x' = 0
The rest of U0j, U1j, U2j, and U33, algebras are not Boolean algebras, because they are missing the unit element.
Similar algebraic structures with two binary operations, product, symmetric difference and 0, without unit, are
generally designated as Boolean rings (Mendelson 1970). Birkoff (1948) shows that there is a one-to-one
correspondence between Boolean algebras and Boolean rings with unit. He calls a relatively complemented
distributive lattice with 0, generalized Boolean algebra. Tarski (1956) examines the generalized Boolean algebras
as Boolean rings. And since for every non-empty shape y , belonging to an algebra of lines, planes or solids, there
are potentially infinitely many elements x divisible by y, the ring is atomless.
Accordingly, the quadruple ( Uij, +, •, 0 ) forms a commutative, atomless Boolean ring such that for any three
shapes a, b, c, the following seven relations hold
(a + b) + c = a + (b + c)
(a • b) • c = a • (b • c)
a + b = b + a
a • (b + c) = (a • b) + (a • c)
a + 0 = a
(b+ c) • a = (b • a) + (c • a)
for every shape a there is a unique a' such that a + a' = 0
a • a = a
a • b = b • a
All relative complements can be uniquely defined, and the shape algebras Uij can be augmented with the
operation of difference. If a, b belong to some algebra Uij then the difference a – b can be uniquely defined as the
relative complement of b within the closed interval [0, a+b], since 0 < b < a+b, or the relative complement of a • b
within [0, a], since 0 < a • b < a.
Finally, the practical usefulness of spatial transformations such as translations, rotations, reflections, and scaling,
in the manipulation of shapes, calls for an extension of shape algebras to include such transformations. In Stiny
1992 algebras are defined as closed to the Euclidean transformations. A Euclidean transformation t acting on a
shape s is denoted by t(s). Two shapes are geometrically similar when there is a transformation t that makes the
first identical to the second.
Krstic (1996) describes two alternatives for including the transformations in the algebras Uij. The first, includes
transformations t( ) as operators in the set of operations acting on the set {Uij} of shapes. This turns algebras Uij,
into generalized Boolean algebras with infinite operators. The second option is to include the transformations Tj,
in the set {Uij}. This turns shape algebras into two-sorted algebras {Uij, Tj}, with a Boolean part that handles
structure and a group part that handles symmetry. A detailed account on the importance of symmetry
transformations can be found in Economou 1999.
The initial definition of Stiny (1992) regarding the Euclidean transformations is followed in this study.