Geometric elements

Points, lines, planes, and solids are respectiive 0D, 1D, 2D, and 3D geometric elements that will serve as the building blocks of shapes.They are situated in the 3D space, but less than 3D elements could be situated in less than 3D spaces as well. A line can be in the space, but also on an infinite plane or an infinite line. At the minimum, a point can be situated on a point, which is a 0D space. In general, a geometric element is characterized by its dimensionality and the dimensionality of the space it is defined in. Typically, a geometric element of dimension i defined in the space of dimension j ≥ i is denoted by a_ij with all the combinations shown in Table 1.

Table 1. Geometric elements a _ij of dimension i defined in the space of dimension j (j ≥ i) enumerated

It is clear from the table that the minimum space (in terms of its dimensionality) in which a single geometric element can be defined is of the same dimension as the geometric element itself. Elements defined in their minimum spaces are diagonal geometric elements as they appear on the diagonal of the table. The minimum space for a set of geometric elements could be as small as the minimum space of one of the elements and as big as the 3D space. For example, the minimum space for two collinear lines is 1D, for two parallel or two intersecting lines is 2D, while for two skew lines is 3D. If the minimum space of a nonempty set of geometric elements is the same as the minimum space of one of its elements, then it is a diagonal set and the space is a diagonal space. It is easy to see that in such a set all elements have the same minimum space. For example, the set of all solids is diagonal, but so is a set of collinear lines.

Boundaries of geometric elements

Boundaries outline geometric elements. Each geometric element is delineated by a finite collection of geometric elements one dimension smaller than itself. Two endpoints delineate a line, a polygon delineates a plane, and a closed polyhedral surface delineates a solid. Points do not have boundaries and lines have two-point boundaries. Given that each geometric element of dimension greater than 0 has infinitely many geometric elements embedded in it, the boundary of a geometric element of dimension greater than 1 can be described by an infinite set of geometric elements. However, the fact that there are also finite descriptions qualifies it as a boundary. There are figures with finite areas and infinite boundaries, that is, boundaries that cannot be described by finite sets. For example, the Koch snowflake in Figure 1 is a finite area planar figure which may have a fractal boundary with an infinite number of lines.

Fig. 1. Koch snowflake: a finite area planar figure which may have an infinite fractal boundary.

Calculating with geometric elements

Geometric elements could be related in many ways. One could be embedded in or be coincident with another element or the two could overlap or touch. There are numerous other relations but these four play important roles when calculating with geometric elements. The most important relation is embedding. Intuitively, given two lines, the first line is embedded in the second one, if the result of drawing one on top of the other is the second line. The first line appears to be a part of the second one. The embedding relation is a partial order ≤ on a set of geometric elements of the same kind – that is, the elements of the same dimension defined in the same space. Note that this implies that only lines could be parts of lines, planes parts of planes, and solids parts of solids. A point can be coincident with a line but not its part. However, for a ≤ b to hold, where a and b are geometric elements, being of the same kind is not enough. There is another necessary – but not sufficient – condition: set {a, b} must be diagonal.

For points, partial order is identity. A point is a part of another point if the two are identical. That is if a ≤ b, then b ≤ a and a = b, where a and b are points. Note that for points, all diagonal sets are singletons.

Armed with partial order we may proceed to define Boolean operations: product, sum, difference, and symmetric difference – for geometric elements of the same kind belonging to the same diagonal set.

For points defined on a point (0D space), sum and product are always defined and equal to the only point, which is both the smallest and the greatest element. In contrast, difference and symmetric difference are never defined. Points defined in 1D, 2D, and 3D spaces have sum and product only if the points that are arguments are identical. In contrast, difference is only defined if the arguments are different points, while symmetric difference is never defined. Geometric elements of higher dimension have more elaborate behavior in calculations. Operations for lines planes and solids are defined below.

Product: a⋅b = c exists if c is the greatest common part of a and b. That is c ≤ a and c ≤ b so that set {a, b, c} is diagonal. Given the lines in Figure 2a, the top one is the product of the middle and the bottom line. Two lines in (b) belong to a diagonal set but do not have the product as there is no line that is part of both. It is clear from the definition and examples that for a⋅b to be defined a and b must have common parts – that is, overlap – however, this is not sufficient for planes and solids. For example, two overlapping L-s (c) do not have a product. The greatest common part is missing, as we end up with two incomparable elements (d).

Fig. 2. Product: the top line is the product of the other two (a); there is no product of the two lines (b); there is no product of the two overlapping L-s (c) as there is no smallest common part (d).

Sum: a + b = c if c is the smallest geometric element with both a and b as parts (1), and there is no part of c that does not share parts with a or b (2). If sum exists, then a ≤ c and b ≤ c so that set {a, b, c} is diagonal. Given lines in Figure 3a, the top one is the sum of the middle and the bottom line. In contrast, with lines (b) the top one is the smallest line with the bottom two as parts, but it is not their sum. It satisfies condition (1), however, the gap between the bottom lines can accommodate infinitely many lines that violate condition (2). Both conditions (1) and (2) are required only for lines. For planes and solids, condition (1) is sufficient. For example, neither planes (c) nor planes (d) satisfy (1) and cannot be summed. In contrast, planes (e) and planes (f) do satisfy (1) so that (g) and (h) are their respective sums. The sums exist because planes overlap in the first case and touch in the second.

Fig. 3. Sum: top line is the sum of the other two (a); top line is not the sum of the other two (b); pairs of planes (c) and (d) do not have sums; pairs of planes (e) and (f) and their respective sums (g) and (h).

The touch relation could now be defined: geometric elements touch if their sum exists, but their product does not.Footnote ⁴

Difference: a – b = c exists if c is the greatest part of a that does not share parts with b. Given lines in Figure 4a, the top line is the result of subtracting the middle line from the bottom one. The same result we get if the middle line is subtracted from the top one and we get the middle line if the two arguments swap their places. That is, a – b = a and b – a = b if the two do not have common parts. There is no difference defined for lines (b) as we end up with two or no geometric elements depending on the order of arguments. There is another, somewhat unintuitive, requirement stemming from the Boolean nature of the operations. As there is no greatest or smallest geometric element, difference is defined using relative complements. It is the unique complement of b relative to the interval [b, a + b]. Thus, the difference could only be defined if a + b is defined. This is stricter than the usual diagonal set requirement.

Fig. 4. The top line (a) is the result of subtracting the middle line from the bottom, or if the middle line is subtracted from the top one, and the middle line is the result of arguments swapping their places; there is no difference or symmetric difference for two the lines (b); each of the three lines (c) is the symmetric difference of the other two; the two overlapping L-s in Figure 2c yield two possible differences (d) and (e) and the symmetric difference (f).

Symmetric Difference: a ⊕ b = c exists if c is the greatest geometric element with each of its parts being either part of a or b, but not of both. For example, each of the three lines in Figure 4c is the symmetric difference of the other two. In contrast, lines (b) do not have the symmetric difference as two different lines satisfy the definition. Like the other operations, the symmetric difference is only defined for diagonal sets of arguments.

Although the operations above are Boolean in nature, some of the standard Boolean identities do not hold. For example, the definition of difference as the unique complement of a⋅b relative to the interval [a⋅b, a], which is equivalent to the one given before, does not hold if a⋅b is not defined although the difference may be defined. Similarly, if a – b exists, then a – b = a – (a⋅b) should hold. For example, the two overlapping L-s in Figure 2c yield two possible differences, as shown in Figure 4d,e. However, the identity does not hold for either of the differences because the product of the L-s is not defined. Likewise, the symmetric difference of the two L-s is (f), which is the following standard identity a ⊕ b = (a – b) + (b – a). However, another standard identity a ⊕ b = (a + b) − (a⋅b) does not hold for the lack of product.

Note that the geometric elements that are results of the operations above have finite boundaries because the elements that are the arguments of the operations have finite boundaries.

Set I_ij of all geometric elements of dimension i defined in the space of dimension j together with operations ⋅, +, −, and ⊕ forms partial algebra I_ij – which is partial because I_ij is not closed under the operations.

Defining shapes

Calculations with geometric elements are purely spatial: one starts with two geometric elements and transforms them into one usually different than both – but occasionally equal to one of them. Such a transformation depends on a spatial relation between geometric elements and may not always be possible. In contrast, nonspatial or symbolic calculations are always possible as they typically involve just repacking geometric elements while leaving them intact. One may take two elements from two packages and place them into one: {a} ∪ {b} = {a, b}; or may take some elements out of a package and not worry if the package ends up empty: {a, b}\{a, b} = {} = Ø. The packages are more important than the elements they contain so the latter are as good as symbols. In order for calculations with geometric elements to always be defined, I_ij should be extended to include nonspatial (set) operations. Consequently, geometric elements are replaced with sets of geometric elements of the same kind, or shapes. Shapes are combinations of the spatial and nonspatial. The spatial is what matters the most while the nonspatial is there for closure, that is, to be able to calculate and always get the result.

For example, one cannot make a line out of the two lines in Figure 2b so the sum from I ₁₁ fails. However, if each line is seen as a one-line shape, then the set union produces a two-line shape and we have the sum. Similarly, if the top line in Figure 4b is subtracted from the bottom one, no geometric element is left, and the difference fails. Not so if the two lines are shapes. The difference produces a shape with no geometric elements, just an empty set.

Geometric elements forming a shape must, be of the same kind, and occupy a finite chunk of space. Because there are infinitely many geometric elements embedded in a single geometric element – if its dimension is greater than 0 – different sets, including infinite ones, of geometric elements may represent the same shape. An infinite set may represent a shape if there is at least one finite set representing the same shape. The following proposition establishes bounds for such sets.

Proposition 1: Let a and A be sets of geometric elements defined in I_ij and confined to a finite chunk of space. Let a be finite with sums being defined only for pairs of identical elements (i) and let A be the set of all elements that are parts of elements of a, or A = {x ≤ y | y ∈ a} (ii). The following holds:

1. (1) a is the set of maximal geometric elements of A,

2. (2) a represents a shape, and

3. (3) A is the set of all geometric elements embedded in the shape represented by a.

Proof: From (i), a is a set of maximal elements, and from (ii), a ⊆ A so that these are also maximal elements of A, which proves (1). a must have a finite boundary to be a shape. Because a is finite and so are the representations of boundaries of elements of a, the union of these representations is finite and is a representation of the boundary of a, which proves (2). Assume (3) does not hold so that there is a geometric element z embedded in the shape represented by a such that z ∉ A. Thus, z must be a sum of parts of different elements of a. From (i), no such sum exists so that (3) holds.

Sets a and A are, in terms of their cardinalities, respective minimal and maximal sets representing the same shape. The former one is the ideal shape representation because it is unique and compact which leads to the following three equivalent definitions of shape.

A shape occupies a finite chunk of space and is:

1. (1) A finite set of geometric elements defined in I_ij such that only pairs of identical elements have sums.

2. (2) A finite set of maximal geometric elements defined in I_ij.

3. (3) A finite subalgebra of I_ij with sums and products defined only for identical elements.

Note that subset X of partial algebra I_ij is its subalgebra if every sum (product) of elements of X which is defined is also an element of X.

Any finite set of geometric elements from I_ij, occupying a finite chunk of space, may be represented as a shape.

Proposition 2: Let C be such a set and let cl ₊(C) be its closure under sum, where cl ₊ is a closure operator on the set of subsets of C,℘(C). Set a of maximal elements of cl ₊(C) is a shape represented by C.

Proof: Because C is finite cl ₊(C) is finite and there are elements e∈cl ₊(C) such that for every c∈cl ₊(C) e + c = e or is not defined. The set of all elements like e is a and because they are maximal with respect to one another a is a shape. Each element of C is either part of or equal to an element of a because a is the set of maximal elements of cl ₊(C) so that a is the shape represented by C.

The proposition holds for infinite C provided that a exists and is finite and that for every x∈C there is y ∈ a such that x ≤ y. A good example of such a set is A from proposition 1.

Calculating with shapes

Calculations with shapes are combinations of spatial calculations, which alter geometric elements, and nonspatial ones, which just group them. Unlike spatial calculations with geometric elements, which may not always be defined, calculations with shapes always result in shapes.

As with geometric elements operations for shapes are Boolean and depend on the partial order among shapes. The latter is defined as follows.

The Subshape (or a part) a of shape b, or a ≤ b, is a shape where for every x ∈ a there is y ∈ b such that x ≤ y.

The smallest shape is an empty shape which is an empty set of geometric elements denoted by 0. An empty shape is a part of every shape. Note that there are different empty shapes as these are empty sets of elements from different I_ij partial algebras.

The subshape relation is pivotal in defining operations on shapes, but for calculating with them we also rely on operations for geometric elements.

It is important to note that the operations below are defined for shapes occupying the same finite chunk of space. For example, two shapes that are an infinite distance apart cannot be summed. It could be argued that this requirement is unnecessary as “infinite distance” is nowhere to be found in nature, however, some of our representational tools do allow for it. Such an example is provided on page 6 (right column).

Sum: a + b is the smallest shape which has both a and b as parts.

Proposition 3: The sum of shapes a and b is the set of maximal elements of cl₊(a ∪ b).

Proof: Per Proposition 2, set x of maximal elements of cl₊(a∪b) is the shape represented by a∪b. Every element of x is either the sum of elements of both a and b, or is equal to an element of a or b. Thus, x is the smallest shape that includes both a and b as parts or x = a + b.

The sum could be calculated recursively via the following procedure, which uses the sum from I_ij.

Procedure 1:

• Initial values: A₀ = a, B₀ = b, i = 1, 2,…card(b)Footnote ⁵

• Recursive step: B_i = B_{i− 1} \ {b}, where b ∈ B_{i− 1},

  • C = {x if x + b is not defined | x ∈ A_{i− 1}},

  • D = {x + b | x ∈ A_{i− 1} \ C},

  • c = Σ (D ∪ {b}),

  • A_i = C ∪ {c}

• Result: a + b = A_{card (b)}

For i = 1, we remove element b from b (line 1 of the recursive step) and partition a into set C of elements which do not sum with b and a set of ones that do (A_{i− 1}\C), which are then summed with b to get D (lines 2 and 3). D is augmented with b – just in case A_{i− 1}\C was empty – and summed to create geometric element c. All elements of D include b as a part so that their sum is defined. Element c is included in set C of elements which do not sum with b to create A_i. The process is continued until all the elements of b are exhausted (B_{card (b)} = Ø). Note that each A_i is a shape – a set of maximal elements – and so is the result A_{card (b)}. The set U_ij of i-dimensional shapes defined in the j-dimensional space closed under + and ⋅ is a relatively complemented distributive lattice ordered by the subshape relation. It features an empty shape as the smallest element while lacking the greatest one. Being distributive makes its relative complements unique, enabling the definition of the difference operation.

Difference: a – b is the relative complement of b with respect to interval [0, a + b], or dually the relative complement of a⋅b with respect to interval [0, a]. It is the greatest shape made only of parts of a which have no parts that are parts of b.

Difference could be calculated recursively via the following procedure that utilizes the difference of I_ij.

Procedure 2:

• Initial values: A₀ = a, B₀ = b, i = 1, 2,…card(b)

• Recursive step: B_i = B_{i− 1} \ {b}, where b ∈ B_{i− 1},

  • C = {x if x – b is not defined | x ∈ A_{i− 1}},

  • D = {x – b | x ∈ A_{i− 1} \ C},

  • A_i = C ∪ D

• Result: a – b = A_{card (b)}

Product: a⋅b is the greatest shape embedded in both a and b. To calculate it, we rely on the difference for shapes which is related to the product via a⋅b = a – (a – b).

Symmetric Difference: a ⊕ b is the greatest shape having only parts of a that have no parts that are parts of b and parts of b that have no parts that are parts of a. To calculate it, one may use – and + with formula a ⊕ b = (a – b) + (b – a) or equivalently by using –, +, and ⋅ with a ⊕ b = (a + b) – (a⋅b).

For example, the two shapes in Figure 5a have product (b), sum (c), difference (d), another difference (e), and symmetric difference (f).

Fig. 5. Shape operations: two shapes (a) and (b) have the product (c), sum (d), difference (e), another difference (f), and symmetric difference (g).

Boundaries of shapes

We established earlier that the boundary of a geometric element may be represented by a finite set of geometric elements one dimension lower than the original element. However, proposition 2 allows for a more precise characterization of the boundary.

Boundaries of geometric elements are shapes one dimension lower than the elements because the boundary of an i-dimensional geometric element can be represented by a finite set of (i−1)-dimensional geometric elements it can, according to proposition 2, be represented as a shape.

This allows for a unique and compact representation of boundaries and introduction of boundary operator b_e: I_ij → U_{i− 1j}, where U_{i− 1j} is the set of (i − 1)-dimensional shapes defined in the j-dimensional space. The boundary operator takes a geometric element from I_ij to its boundary which is a shape in U_{i− 1j}, or y = b_e(x), x ∈ I_ij, y ∈ U_{i− 1j}. For example, the identity in Figure 6a shows operator b_e turning a quadrilateral planar geometric element into a set of four maximal lines or a linear shape which is a boundary of the planar element. Because shapes are sets of maximal geometric elements, boundaries are sums of the boundaries of the elements. Consequently, the boundary operator for shapes b: U_ij → U_{i− 1j} is defined as b(a) = Σ_{x ∈a} b_e(x) where b(a) ∈ U_{i− 1j}, a ∈ U_ij and x ∈ I_ij. Identity (b) shows how this works for a planar shape having two maximal geometric elements.

Fig. 6. Boundary operators: identity (a) shows operator be turning a quadrilateral planar geometric element into a linear shape which is its boundary; identity (b) shows operator b turning a two-element shape into its linear boundary by summing the boundaries of the elements; sequence (c) of shapes a cube and boundaries obtained by recursive applications of operator b.

Boundaries of shapes are shapes one dimension lower than the original shapes. They are sums of the boundaries of maximal elements representing shapes.

For example, the sequence of shapes in Figure 6c has a 3D solid cube, its boundary which is a 2D shape consisting of 6 planar squares, with a 1D boundary consisting of 12 lines, and its boundary a 0D shape having 8 points, respectively. It is a chain of boundaries of a 3D shape starting with the first-order 2D boundary (or simply the boundary), followed by the second-order 1D boundary, which is the boundary of the first-order boundary, and ending with the third-order 0D boundary, which is the boundary of the second-order boundary. More formally:

m-order boundary of shape a ∈ U_ij is shape b^m(a) ∈ U_i−mj, m ∈ {0, 1, … i} is defined recursively by b ⁰(a) = a, b^{n +1}(a) = b(bⁿ(a)).

There is a trivial, but nicely sounding proposition stemming from this definition.

Proposition 4: All shapes are m-order boundaries of shapes.

Calculations with shapes do not mirror calculations with their boundaries as the two are not isomorphic. For example, for the two singleton shapes in Figure 7a, the boundary of their sum (b) is different than the sum of their boundaries (c). The only exception is the operation of symmetric difference when applied to shapes sharing the same diagonal space.

Fig. 7. Calculations with shapes and boundaries: two shapes (a), the boundary of their sum (b), and the sum of their boundaries (c); shapes (d) with their boundaries (e) have symmetric difference (f) with boundary (g).

Proposition 5: The boundary of the symmetric difference of two diagonal shapes sharing the same diagonal space is the symmetric difference of their boundaries, or b(a ⊕ b) = b(a) ⊕ b(b) where a, b ∈ U_ii (Earl, Reference Earl1997; Krishnamurti and Stouffs, Reference Krishnamurti and Stouffs2004).

Proof: Possible spatial relations between a and b determine how parts of their boundaries are affected by a ⊕ b. A part of the original boundary should be removed if there is either a shape or an empty shape on both of its sides (i) and it should be preserved otherwise (ii). If b(a) ⋅ b(b) = 0 and either a ⋅ b = 0 or b < a or a < b, then a ⊕ b is a + b or a – b or b – a, respectively. In all three cases, boundaries of a and b satisfy (ii) and should be preserved which b(a) ⊕ b(b) = b(a) + b(b) does so that b(a ⊕ b) = b(a) ⊕ b(b) (iii) holds. If b(a) ⋅ b(b) ≠ 0 and either a ⋅ b = 0 or b < a or a < b, then a ⊕ b is a + b or a – b or b – a, respectively. In all three cases, b(a) ⋅ b(b) satisfies (i) and should be removed which b(a) ⊕ b(b) = [b(a) + b(b)] – [b(a) ⋅ b(b)] does so (iii) holds. If a ⋅ b ≠ 0 and b(a) ⋅ b(b) = 0, then a ⊕ b removes a ⋅ b so that b(a ⋅ b) satisfies (ii) and should be preserved. The remaining parts of boundaries b(a) – b(a ⋅ b) and b(b) – b(a ⋅ b) also satisfy (ii) so that both b(a) and b(b) should be preserved which b(a) ⊕ b(b) = b(a) + b(b) and again (iii) holds. This exhausts all the possible spatial relations between a and b and completes the proof.

For example, shapes in Figure 7d with their respective boundaries (e) have symmetric difference (f) with boundary (g). The latter is also the symmetric difference of boundaries of the original shapes. Restriction to diagonal shapes is necessary to avoid situations where the products of boundaries are parts of new boundaries like, for example, the surface of cube Figure 6c with the boundary made of lines that are products of boundaries of the adjacent faces. Because products are never parts of symmetric differences proposition 5 does not hold.

Proposition 5 can be generalized to include different order boundaries.

Proposition 6: The m-order-boundary of symmetric difference of two diagonal shapes sharing the same diagonal space is the symmetric difference of their m-order boundaries, or b^m(a ⊕ b) = b^m(a) ⊕ b^m(b), where a, b ∈ U_ii, and m ∈ {0, 1, … i} (see page 9 (left column) of the proof).

The corollary below extends proposition 6 to nondiagonal shapes of a certain kind.

Corollary: Let shapes a, b ∈ U_ij be m-order boundaries of diagonal shapes from U_jj, where 1 ≤ i < j and m = j – i, then b(a ⊕ b) = b(a) ⊕ b(b) holds.

Proof: Let a = b^m(a′) and b = b^m(b′) so that a ⊕ b = b^m(a′) ⊕ b^m(b′) = b^m(a′⊕ b′) in accordance with proposition 6. Now, b(a ⊕ b) = b(b^m(a′⊕ b′)) = b^m + 1(a′⊕ b′) = b^{m +1}(a′) ⊕ b^{m +1}(b′) =b(b ^m(a′)) ⊕ b(b ^m(b′)) = b(a) ⊕ b(b) in accordance with proposition 6 and the definition of m-order boundaries.

Propositions and the corollary above are global in nature as they consider shapes of certain kinds without considering their spatial relations. Sharper results could be achieved by considering some local properties. For example, the corollary of proposition 6 is sharpened by the proposition below (which is given without the proof).

Proposition 7: Let the product of shapes a, b ∈ U_ij be the m-order-boundary of a diagonal shape from U_jj, where 1 ≤ i < j and m = j – i, then b(a ⊕ b) = b(a) ⊕ b(b) holds.

Two-sorted algebras of shapes

An algebra of shapes should have a Boolean part to handle the structures of shapes and a group part to deal with their symmetries (Krstic, Reference Krstic1999, Reference Krstic and Gero2014).

The Boolean part has set U_ij of shapes, occupying a finite chunk of space, which together with Boolean operations forms a relatively complemented distributive lattice with the least element, but without the greatest one. Such a structure is due to its Boolean properties also known as Generalized Boolean Algebra (Birkhoff, Reference Birkhoff1993).

The group part has set T_ij of similarity transformations that can act on i-dimensional shapes defined in a j-dimensional space. Set T_ij is closed under group operations of composition °, inverse ⁻¹, and identity ι, to form group T_ij. This structure allows for calculating with transformations. For example, simple transformations could be combined to create more complex ones, or an inverse of a transformation could be created to undo an erroneous move.

Boolean and group parts are connected via the operation of group action (): T_ij × U_ij → U_ij where shape a is acted upon by transformation t to produce the transformed shape t(a).

Note that T_ij need not be the similarity group of transformations. It could be any group that can act on shapes like the rigid body, Euclidean, affine, or some subgroups of these, or even some unusual ones as a group with shapes as elements (Krstic, Reference Krstic1999).

Boolean and group parts are combined in a two-sorted algebra U_ij with carrier {U_ij, T_ij} having elements of two different sorts – shapes and transformations – and signature {⋅, +, c, ⊕, °, ⁻¹, ι, ()} with Boolean and group operations as well as the group action. Algebras U_ij are enumerated and sorted in Table 2 based on the dimensionality of geometric elements making their shapes (i) and the dimensionality of the space the latter are defined in (j). The table resembles Table 1 of geometric elements. For example, algebras with shapes defined in the minimum space of their geometric elements appear on the diagonal of the table, the same way the elements appeared in the previous table. The geometric elements were diagonal, and the algebras are diagonal operating on diagonal shapes in diagonal spaces.

Table 2. Algebras U_ij enumerated and sorted based on the dimensionality of geometric elements making their shapes (i) and the dimensionality of the space the latter are defined in (j)

As mentioned earlier, a shape has to be confined to a finite chunk of space and the same requirement holds for set U_ij of shapes. Although infinite distances are common in mathematics, they do not appear in nature so that these constraints seem unnecessary. However, there are some methods of 3D object representation that include infinite distances.

For example, the drawing in Figure 8 includes lines in the plane which should belong to a U ₁₂ algebra so that triangle ΔABC is a shape – an element of U ₁₂. There are also (labeled) points A, B, and C which are shapes in a U ₀₂ algebra and so is their sum. In contrast, the drawing can be seen as a perspective representation of a cube. As such it belongs to a U ₁₂ algebra which is now closed under projective transformations in place of the similarity ones. Triangle ΔABC is not a shape in this new algebra. Its sides AC and BC are infinite in length because point C is a vanishing point at infinity for a pencil of parallel lines. Points A, B, and C are now shapes in a U ₀₂ algebra closed under projective transformations. However, their sum is not a shape because it has three points as maximal elements where one is infinitely distanced from the other two. So, it seems that the finite chunk containment requirement should stay after all.

Fig. 8. Perspective drawing of a cube.

Combining algebras of shapes

Shapes in practice often come as compound, having geometric elements of different kinds like the shape in Figure 9a, which has four lines and a planar segment. The lines belong to U ₁₂ while the planar segment belongs to U ₂₂ so that the shape must belong to a combination of the two algebras. A standard algebraic combination is the direct product of component algebras which have the same signatures. Direct product U ₁₂ × U ₂₂ of U ₁₂ and U ₂₂ is a two-sorted algebra of compound shapes with carrier {U ₁₂ × U ₂₂, T ₁₂ × T ₂₂}, which is the Cartesian product of the component carriers and operations defined componentwise. Shape (a) is represented by the ordered pair (b) where the first element is in U ₁₂ and the second in U ₂₂. The componentwise symmetric difference of two compound shapes (a, u), (b, v) ∈ U ₁₂ × U ₂₂ is (a, u) ⊕ (b, v) = (a ⊕ b, u ⊕ v) with an example of such calculations depicted in Figure 9c.

Fig. 9. Compound shapes: shape (a) with linear rectangle and a planar segment represented by ordered pair (b) with first element belonging to U ₁₂ and to U _22.

Likewise, the action of compound transformation (t ₁, t ₂) ∈ T ₁₂ × T ₂₂ on compound shape (a, b) ∈ U ₁₂ × U ₂₂ is (t ₁, t ₂)((a, b)) = (t ₁(a), t ₂(b)) ∈ U ₁₂ × U ₂₂.

For example, the clockface in Figure 10a showing 9:00 is defined in U ₁₂ × U ₂₂. It shows 9:15 (b) after the action of transformation (rot(−90°), rot(−90/12 = −7.5°)) ∈ T ₁₂ × T ₂₂, where rot(x) is the rotation of x degrees around the origin.

Fig. 10. Compound algebras: clockface (a) defined in U ₁₂ × U ₂₂ is showing 9:00; it shows 9:15 (b) when transformed by (rot(−90°), rot(−7.5°)) ∈ T ₁₂ × T ₂₂; shape (c) rotated in a direct product algebra (d) and in a sum of algebras (e).

Another combination of algebras is their sum. Unlike direct product, which is in the domain of universal algebra, sum is particular to algebras of shapes (Krstic, Reference Krstic1999, Reference Krstic and Gero2014). It is based on a subdirect product, that is, a subalgebra of a direct product that enumerates all elements of the component algebras, but not all of their combinations. The sum of two shape algebras is a subdirect product that enumerates all shapes of the component algebras as well as all their combinations but allows only combinations of equal transformations. Sum does not restrict the Boolean part but requires for all components of compound shapes to be transformed in the same way. This preserves the integrity of compound shapes in calculations. For example, the compound shape in Figure 10c could be rotated in the direct product algebra so that its boundary is off (d) however, this cannot happen with the sum of algebras where both the shape and its boundary are rotated in the same way (e).

Natural and diagonal decompositions of shapes

A shape could be decomposed into shapes that are its parts. Given shape a, set A of its parts is a decomposition of a if it is finite and sums up to a, or ΣA = a. Set A is a discrete decomposition of a if for each x, y ∈ A and x ≠ y, x⋅y = 0. There is a unique discrete decomposition of each shape that stems from the shape definition.

The natural decomposition of shape a ∈ U_ij is set n_a with elements that are singleton shapes of maximal geometric elements which define a, or n_a = {{x}| x ∈ a}. For example, the shape in Figure 13a has natural decomposition (b). Each shape has its unique natural decomposition. Because shapes which are elements of the decomposition are incomparable, their sum and union are equal, or Σn_a = ∪n_a = a.

Fig. 13. Natural and diagonal decompositions: shape (a) and its natural decomposition (b); shape (c) and its natural (d) and diagonal (e) decompositions.

Each element of a natural decomposition is singleton shape, so its minimum space is a diagonal one. Two shapes belonging to the same algebra may have natural decompositions such that an element of one decomposition shares diagonal space with an element belonging to a different one. There could be several such pairs of elements. If the two shapes are arguments of some calculation, then calculations with elements sharing the same diagonal space could take place in the related diagonal algebra. This opens interesting possibilities, however, not without a problem. There is no guarantee for two elements of the same natural decomposition to be in different diagonal spaces. Fortunately, there is another discrete decomposition related to the natural one, which overcomes this problem.

The diagonal decomposition of a shape is a discrete decomposition in which each element is a diagonal shape and no two elements share the same diagonal space. The decomposition in Figure 13b is both natural and diagonal. In contrast, shape (c) has decompositions (d) and (e) as natural and diagonal, respectively.Footnote ⁶ Note that the last two shapes in the natural decomposition share the same diagonal space so they are replaced with their sum in the diagonal one. Going the other way, each nonsingleton shape of a diagonal decomposition should be replaced with its natural decomposition to get the natural decomposition of the original shape. Like natural decompositions diagonal ones are unique and also like natural decompositions they sum in a nonspatial way: Σd_a = ∪d_a = a. Let n_a and d_a be the respective natural and diagonal decompositions of shape a, then n_a ≤ d_a and card(d_a) ≤ card(n_a).Footnote ⁷

Now, we are in a position to break calculations with shapes into partial calculations carried on in diagonal algebras defined by the diagonal decompositions of the argument shapes. Let d_a and d_b be the respective diagonal decomposition of shapes a and b from U_ij, and let shapes x ∈ d_a and y ∈ d_b share the same diagonal space. That is to say that set {x, y} is diagonal, or ordered pair (a, b) is diagonal, or shapes x and y are co-diagonal. Partial calculation x * y, where * stands for ⋅, +, −, or ⊕, could be carried on in U_ij, but also in a diagonal algebra U_ii defined in the space that x and y share. Different such pairs may exist and for each of them the above partial calculation is carried on in an appropriate diagonal algebra. The same could be extended to elements that could not be paired by simply pairing them with appropriate empty shapes. Finally, the union of the results of such partial calculations is equal to a * b. So instead of doing a calculation in U_ij we did several simpler calculations in different U_ii algebras.

For example, the calculation in Figure 14 carried out in U ₁₂ can also be done in six diagonal algebras U ₁₁ by using diagonal decompositions of the argument shapes, as shown in Table 3.

Fig. 14. Calculation carried out in U _12.

Table 3. Example, of a calculation with shapes carried out in U ₁₂ and also with diagonal decompositions of the argument shapes carried out in six diagonal algebras U ₁₁

Shapes which are arguments of the calculation in U ₁₂, as well as their diagonal decompositions spanning U ₁₁ algebras, are shown in rows 3 and 4 of the table. Each diagonal decomposition spans four diagonal algebras and both decompositions span six algebras. The resulting shape of the calculation appears in the bottom row together with its decomposition which has nonzero elements in all six diagonal algebras. Calculations in (U ₁₁)₂ and (U ₁₁)₄, where decompositions of both argument shapes have nonzero elements, are spatial: they result in new shapes. The calculations in the rest of the algebras are nonspatial with the nonzero argument as the result. Note that the decomposition of the resulting shape is also diagonal.

Because diagonal decompositions are unique, we may introduce operator d: U_ij → ℘(U_ij) that takes a shape to its diagonal decomposition, or d(a) = d_a. The calculation above exposed an interesting property of diagonal decompositions, d(a + b) = d(a) + d(b), where + on the right side is carried out componentwise. This remains true for other Boolean operators (⋅, −, ⊕), which gives rise to an algebra of diagonal decompositions.

Algebras of diagonal decompositions of shapes

The uniqueness of diagonal decompositions – that is, their 1-1 relation to shapes – as well as the expressions like the one above render an algebra of diagonal decompositions isomorphic to an appropriate algebra of shapes. This is expressed by commutative diagram ${\boldsymbol U}_{{{\boldsymbol ij}}\enspace} {}_{d}\!\! \mathbin{\lower.3ex\hbox{$\buildrel\textstyle\rightarrow\over {\smash{\leftarrow}\vphantom{_{\vbox to.5ex{\vss}}}}$}} \!\!{}^{_{\cup}} \ {{\boldsymbol X}_{{\boldsymbol ij}}}$, where X_ij is an algebra of diagonal decompositions of shapes from U_ij.

Table 3 may provide some guidance on how to do Boolean operations in X_ij.

Let two shapes a and b defined in U_ij be arguments of calculation a * b = c, where * stands for ⋅, +, −, or ⊕. To do the calculation with diagonal decompositions in place of shapes, we may use the following procedure.

Procedure 3:

1. 1. Define diagonal decompositions of U_ij implied by d(a) and d(b), that is, A = {U_ii | x ∈ d(a), x ∈ U_ii} and B = {U_ii | x ∈ d(b), x ∈ U_ii}.

2. 2. Calculate sets of diagonal algebras which are in B but not in A or in A but not in B, that is,. A′ = B\A and B′ = A\B.

3. 3. Augment decompositions d(a) and d(b) with empty shapes of algebras from sets A′ and B′, that is, d(a)′ = d(a) ∪ {0 ∈ U_ii | U_ii ∈ A′} and d(b)′ = d(b) ∪ {0 ∈ U_ii | U_ii ∈ B′} so that card(d(a)′) = card(d(b)′).

4. 4. Calculate d(c)′ = {x * y | x ∈ d(a)′, y ∈ d(b)′, x, y ∈ U_ii, U_ii ∈ A ∪ B}.

5. 5. Finally calculate d(c) = {x ∈ d(c)′ | x ≠ 0}.

Because a U_ij algebra includes transformations, one would expect that a related algebra of diagonal decompositions includes them as well. However, it only handles the Boolean part while leaving the transformations to U_ij. Diagonal decompositions and their algebras streamline spatial calculations with shapes by breaking them down into simpler calculations with parts of the shapes. The latter calculations are independent with respect to one another and could be done in parallel. The same approach may be used for checking the partial order among shapes by comparison of their parts done in parallel. A diagonal decomposition could easily be turned into the related natural decomposition – which is the standard maximal representation of a shape – and vice versa.

To showcase the utility of diagonal decompositions, we will use them to provide a rather elegant proof of proposition 6 – which has been left unproven on page 6 (left column).

Proof of Proposition 6: We will prove by induction on m validity of b^m(a ⊕ b) = b^m(a) ⊕ b^m(b), where a, b ∈ U_ii and m ∈ {0, 1, … i}. It trivially holds for m = 0 stating that a ⊕ b = a ⊕ b. Assuming that it holds for n, 1 ≤ n < m, we have to prove that it holds for n + 1. Because it holds for n, d(bⁿ(a ⊕ b)) = d(bⁿ(a)) ⊕ d(bⁿ(b)) also holds. Now, let elements x_a⊕b ∈ d(bⁿ(a⊕b)), x_a ∈ d(bⁿ(a)), and x_b ∈ d(bⁿ(b)) of diagonal decompositions belong to the same diagonal algebra U_{i −n i−n}. Because these are diagonal shapes (*) b(x_a⊕b) = b(x_a) ⊕ b(x_b) holds by proposition 5. Identities (*) hold for every diagonal algebra induced by the above diagonal decompositions. By summing all of these identities, we get (**) b(bⁿ(a⊕b)) = b(bⁿ(a)) ⊕ b(bⁿ(b)) in accordance with the definition of shape boundaries. Identity (**) is b^{n +1}(a ⊕ b) = b^{n +1}(a) ⊕ b^{n +1}(b) by the definition of m-order boundaries which completes the proof.

With the aid of diagonal decompositions, we were able to break the problem into smaller chunks for which proposition 5 holds and get the result by summing them back to shapes.

Direct sum representation of an algebra of shapes

In the calculations above – as specified by procedure 3, algebra U_ij is de facto decomposed into a finite set of different diagonal algebras U_ii each of which is tasked with a partial calculation. The union of the partial results is the final one. Each diagonal decomposition of a shape defined in algebra U_ij induces the decomposition of U_ij into a set of diagonal algebras U_ii. The decomposition is relative to the shape as it is induced by the shape's diagonal decomposition which is unique. Thus, for each shape a ∈ U_ij, there is the diagonal decomposition of U_ij relative to a denoted by d_ij(a). However, many shapes could have the same diagonal decompositions of U_ij. Let a, b, c ∈ U_ij such that a and b are arguments and c is the result of a calculation carried out in U_ij, then the decomposition relative to the calculation is d_ij(a) ∪ d_ij(b) while the decomposition related to the result of the calculation or d_ij(c) can be any subset of d_ij(a) ∪ d_ij(b) including the empty one.

For example, decompositions of algebra U ₁₂ relative to shapes in the calculation in Figure 11f are {(U ₁₁)₁, (U ₁₁)₂, (U ₁₁)₃, (U ₁₁)₄} and {(U ₁₁)₂, (U ₁₁)₄, (U ₁₁)₅, (U ₁₁)₆} for arguments and {(U ₁₁)₁, (U ₁₁)₂, (U ₁₁)₃, (U ₁₁)₄, (U ₁₁)₅, (U ₁₁)₆} for the result – as shown in Table 3. The resulting decomposition is, in this case, the union of the argument ones, which is also the decomposition relative to the calculation itself.

Algebras of diagonal decompositions as they are defined so far are good enough for practical applications, however, to make them formally sound we need some more work.

For each calculation, U_ij is decomposed into a finite set of U_ii algebras which are considered components so that calculations are done componentwise. The pool of possible U_ii algebras is infinite for all algebras with i < j. For diagonal algebras (i = j), it is a one-member family: the algebra itself. The pool of algebras is represented by the family (U_ii)_{k ∈S}, where S is an infinite indexing set.

For example, a U ₁₂ algebra, with elements which are line segments in a plane has pool (U ₁₁)_{k ∈S} which is the set of diagonal algebras manipulating line segments on infinite lines coincident with that plane. Note that not all U ₁₁ algebras are elements of (U ₁₁)_{k ∈S} but only those whose spaces are coincident with the space of U ₁₂.

Diagonal algebra U_ii is coincident with a U_ij algebra if its space is coincident with that of U_ij.

We can construct a direct product algebra from the diagonal algebras of (U_ii)_{k ∈S}:

$$Q = \prod\nolimits_{{_k }_{{\in} S}} {{( {{\boldsymbol U}_{{\boldsymbol ii}}} ) }_k}.$$

Because S is an infinite set, Q is an infinite direct product with elements which are infinite tuples containing one element from each of the component diagonal algebras. Tuples with all but finitely many elements being 0 correspond to the diagonal decompositions of shapes. For example, the tuple corresponding to d(a), a ∈ U_ij, will have shapes from d(a) at positions corresponding to diagonal algebras from d_ij(a) and empty shapes elsewhere. Such tuples form an infinite direct sum algebraFootnote ⁸ which is isomorphic to U_ij.

Proposition 8: Every U_ij algebra is isomorphic to the direct sum of diagonal algebras U_ii which are coincident with U_ij, or

$${\boldsymbol U}_{{\boldsymbol ij}} = {\oplus} _{k\in S}( {{\boldsymbol U}_{{\boldsymbol ii}}} ) _k,$$

where the identity above holds up to isomorphism. Note that symbol ⊕ above denotes direct sum, however, it stands for symmetric difference everywhere else in the text.

The proposition above describes the diagonal decomposition of U_ij which could also be seen as its direct sum representation. Note that infinite tuples are more elegant representations of shapes than diagonal decompositions. They both do the same job when calculating with shapes, however, the former do it in the standard componentwise way while the latter rely on a proprietary procedure (procedure 3). For i < j, we have an infinite direct sum, while for i = j, we have one component direct sum which is the original diagonal algebra with a twist: its elements are singletons containing shapes.

Like U_ij the direct sum algebra is closed under similarity transformations. These involve spatial transformations carried out in diagonal algebras as well as (nonspatial) permutations of index set S.

Boundary-paired diagonal decompositions and their algebras

So far, we have been following Krstic (Reference Krstic2001) in developing UB_i algebras, but will now use devices developed in this paper to lift the restriction of UB_i algebras to diagonal shapes.

First, the corollary of proposition 6 and proposition 7 allow for the immediate extension of proposition 5 to shapes which need not be diagonal, but either they or their products are m-order boundaries of diagonal shapes. Further extension – to (all) shapes – may be achieved via diagonal decompositions.

Unlike B_i set B_ij ⊂ U_{i −1j} of boundaries of shapes from U_ij cannot be elevated to an algebra. Instead, we approximate shapes from U_ij with a special kind of diagonal decomposition.

The boundary-paired or b-paired diagonal decomposition of a shape is the diagonal decomposition in which every element is paired with its boundary. Because both the diagonal decomposition and boundary are unique for a shape so is its b-paired diagonal decomposition. Thus, we may introduce operator d′: U_ij → ℘(U_ij × U_{i −1j}) which takes a shape from U_ij to its b-paired diagonal decomposition. Operator d′ is defined as d′(a) = {(x, b(x))| x∈d(a)}, a∈U_ij. To go the other way, from b-paired diagonal decompositions to shapes and their boundaries, we make use of projection operators pr_u(d′(a)) = {x| (x, y)∈d′(a)} and pr_b(d′(a)) = {y| (x, y)∈d′(a)} so that a = ∪[pr_u(d′(a))] and b(a) = Σ[pr_b(d′(a))], where a∈U_ij and b(a)∈U_{i −1j}. Like diagonal decompositions the b-paired ones form algebra UB_ij, however, this one has only one operation: symmetric difference ⊕. Like algebras for diagonal decompositions, UB_ij algebras handle only the Boolean part while leaving the transformations to U_ij.

Proposition 9: Let d′(a) and d′(b) be b-paired diagonal decompositions of shapes a, b∈U_ij. The following holds:

1. (1) Each element (x, b(x))∈d′(a) is an element of some UB_i algebra.

2. (2) b-paired diagonal decompositions are closed under symmetric difference, or d′(a ⊕ b) = d′(a) ⊕ d′(b), and form algebra UB_ij.

Proof: If (x, b(x))∈d′(a), then x∈d(a) so that x∈U_ii, for some U_ii, therefore, (x, b(x))∈UB_i, which proves (1). (2) follows from (1), the fact that d(a ⊕ b) = d(a) ⊕ d(b), and proposition 5, that is, b(a ⊕ b) = b(a) ⊕ b(b).

It follows from (1) that d′(a) implicitly defines a set A of UB_i algebras to which its elements belong, or A = {UB_i | x∈d′(a), x∈UB_i}. Consequently, calculation d′(c) = d′(a) ⊕ d′(b) can be compartmentalized and carried on in parallel via a procedure not unlike the one for diagonal decompositions.

Procedure 4:

1. 1. Define sets A and B of UB_i algebras to which elements of d′(a) and d′(b) respectively belong, as well as their relative complements A′ = B\A and B′ = A\B.

2. 2. Augment decompositions d′(a) and d′(b) with empty shapes of algebras from sets A′ and B′, that is, d′(a)′ = d′(a) ∪ {(0, 0)∈UB_i | UB_i∈A′} and d′(b)′ = d′(b) ∪ {(0, 0)∈UB_i | UB_i∈B′}.

3. 3. Calculate d′(c)′ = {(x ⊕ u, y ⊕ v)|(x, y)∈ d′(a)′, (u, v)∈ d′(b)′, (x, y), (u, v)∈UB_i, UB_i∈A ∪ B}.

4. 4. Finally, calculate d′(c) = {(x, y) ∈ d′(c)′ | x ≠ 0, y ≠ 0}.

For example, Figure 15a depicts a calculation carried on in a U ₂₃ algebra – where symmetric difference of a “smaller-than” and “greater-than” shape results in an “X” shape. Table 4 shows how the same calculation looks when done with b-paired diagonal decompositions in place of the shapes. Argument shapes, their boundaries, and their b-paired diagonal decompositions are in the third and fourth rows of the table while resulting shape, its boundary, and its b-paired diagonal decomposition occupy the fifth row.

Fig. 15. Calculation in U ₂₃ algebra (a); the resulting shape obtained from its decomposition by a nonspatial calculation (b) and its boundary by a spatial calculation (c); calculation carried out in U ₁₃ yields an incomplete boundary (d).

Table 4. Calculation in Figure 15a done with b-paired diagonal decompositions in place of the shapes. Argument shapes, their boundaries, and their b-paired diagonal decompositions are in the third and fourth rows of the table while resulting shape, its boundary, and its b-paired diagonal decomposition occupy the fifth row

The resulting “X” shape is obtained from its decomposition via nonspatial calculation (b). In contrast, spatial calculation (c) produces the boundary of “X”. Note that the original calculation (d) carried on in a U ₁₃ algebra results in an incomplete boundary of “X”.

Generalization of UB_i and UB_ij algebras

Based on proposition 6, we may extend b-paired diagonal decompositions to include m-order boundaries so that UB_i and UB_ij algebras could manipulate multiple representations of shapes in parallel.

For example, the sequence of four shapes in Figure 6c may be seen as a solid cube represented by its faces, its edges, and its vertices. It could also be seen as a sequence of m-order boundaries b ⁰(a), b ¹(a), b ²(a), b ³(a), where a is a solid cube belonging to a U ₃₃ algebra. Let b be another shape, say another cube, from U ₃₃, then in accordance with proposition 6 and definition of ⊕ the following holds:

• b^m(a + b) = b^m(a) ⊕ b^m(b), for a⋅b = 0,

• b^m(a – b) = b^m(a) ⊕ b^m(b), for b ≤ a,

• b^m(b – a) = b^m(a) ⊕ b^m(b), for a ≤ b,

• b^m(a ⊕ b) = b^m(a) ⊕ b^m(b), otherwise,

where m ∈ {0, 1, 2, 3}.Footnote ⁹ This means that we can meaningfully calculate with shapes while simultaneously accounting for their different representations. Algebras UB_i and UB_ij could be extended to their respective generalized versions ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ and ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{{\boldsymbol ij}}$, to provide a framework for such calculations.

Elements of a ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ algebra are n-tuples (b^{k 1}(a), b^{k 2}(a), … b^kn(a)) where k ₁ = 0 < k ₂ < ⋯ < k_n ≤ i, and 1 ≤ n ≤ i + 1. The first element of the n-tuple is the shape itself (b⁰(a) = a) followed by an ordered – not necessarily complete – sequence of m-order boundaries. For example, the cube in Figure 6c may be represented by triplet (b ⁰(a), b ²(a), b ³(a)), that is, by itself, its edges and its vertices. Algebras ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ are generalizations of both UB_i and U_ii algebras in the sense that for n = 2 and k ₂ = 1, ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ becomes UB_i, and for n = 1, it becomes U_ii. Calculations in ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ are done componentwise as in UB_i except that the number of components may be different.

Algebras UB_ij can be generalized in a straightforward fashion. Because their elements are b-paired decompositions with components belonging to different UB_i algebras by replacing the latter with ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{\boldsymbol i}$ algebras, we get ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{{\boldsymbol ij}}$ ones. Again, for n = 2 and k ₂ = 1, ${\boldsymbol U}{\boldsymbol {B}^{\prime}}_{{\boldsymbol ij}}$ becomes UB_ij, and for n = 1, it becomes U_ij.