6.1.1 General definitions

[S, G] is called a topologic space iff G is a family of subsets of S that has the following three properties:

G is called a topology on S, and its elements are called open sets. M ⊆ S is called closed iff its complement is open. It follows from T2 and T3 that the family of closed subsets of S is closed under finite unions and arbitrary intersections.

The interior M° of M ⊆ S is the union of all open subsets of M. The closure M^• of M is the intersection of all closed subsets of S that contain M. Set M is open iff it coincides with its interior and closed iff it coincides with its closure. is called the frontier of M.

The degenerate topology , in which every subset of S is open as well as closed, is a topologic space. In this topology, we have M^• = M° = M and ∂M = ø for every M ⊆ S. (The degenerate topology is called the “discrete topology” in most books about topology, but this would not be appropriate in a book about digital geometry.)

Any metric space [S,d] induces a topology on S; see Section 3.1.7. In this topology, the closure M* is the set of all p ∈ S such that d(p, M) = 0.

The Euclidean metric d_e induces the Euclidean topology on (n ≥ 1). For example, for n = 1, an open interval (x,y) = {z ∈ : x <z < y} (x,y ∈ ; x <y) is an open set, and a closed interval [x,y] = {z ∈ : x ≤ z ≤ y} is a closed set.

The binary metric d_b induces the degenerate topology on any set S. The metrics d_α, α ∈ {4,6,8,18,26} (see Section 3.2.2) and∂_α, α ∈ {0,1,2} (see Section 3.3.1) also induce the degenerate topology on or (the grid point model) and on (the grid cell model).

Nondegenerate topologies can be defined on discrete sets. In particular, the open sets of Section 5.1.4 define a topology on any incidence pseudograph. We will discuss these topologies in detail later in this chapter.

Let [S, G] be a topologic space and M ⊆ S; then [M, G_M] is also a topologic space, where G_M = {A ∩ M : A ∈ Z}. G_M is called the inherited topology on M, and M is called a topologic subspace of S. Note that M itself is both open and closed in G_M. (The inherited topology is also called “relative topology” in topology textbooks.)

Maximum connected subsets of M are called components of M.

[S, G] is called an Aleksandrov¹ space or Aleksandrov topology iff any intersection of open sets is open. If S is finite, any [S, G] is Aleksandrov.

For example, in the Euclidean topology ¹ on , an open interval (x,y) is a neighborhood of any z ∈ (x,y), and a closed interval [x,y] is a neighborhood of z ∈ [x,y] iff z ≠ x and z ≠ y.

In an Aleksandrov space, the intersection U (p) of all neighborhoods of p ∈ S is the smallest neighborhood of p, which is also called the star of p. Evidently, U (p) must be an open set. U may not define a symmetric relation on S; we can have q ∈ U (p) but .

[S, G] is called a Kolmogorov space or T₀-space iff, for any two distinct points of S, at least one of them has a neighborhood that does not contain the other.² The degenerate topology is a T₀-space. An Aleksandrov topology is T₀ iff, for every two distinct points p and q, U(p) and U(q) are distinct.

For example, in the topology induced by a metric space, the set of all ε -neighborhoods is a basis. The set of all open intervals of is a basis of the Euclidean topology ¹. In an Aleksandrov topology, the set of all smallest neighborhoods is a basis.

A topologic space has a countable basis iff it has a basis of cardinality of at most N₀, where N₀ is the cardinality of the set of natural numbers. For example, the set of all open intervals with rational endpoints is a countable basis of ¹.

6.1.2 Poset topologies

A reflexive, antisymmetric (for all pairs p and q such that p ≠ q), transitive binary relation on a set S is called a partial order and is denoted by . [S,] is called a partially ordered set (poset, for short).

Any poset topology is Aleksandrov. Following [9], we know that there is a one-to-one correspondence between Aleksandrov topologies on a set S and quasiorders (reflexive and transitive relations) on S, and a quasiorder is a partial order iff the corresponding Aleksandrov topology is T₀. An open set defines an “upper set” of the quasiorder (in the sense of Definition 6.4), and the order “less than or equal to” corresponds to “is in the closure of.”

The incidence grid topology (see Section 6.2.3) is an example of a poset topology. Another example is the following:

(6.1)

In this example, {i}⊆{i}, {i,i + 1}⊆{i,i + 1}, {i}⊆{i,i + 1}, and {i + 1}⊆{i,i + 1} are the only instances of the partial order . This is a T₀-space. In this topology, {{i, i + 1}} and {{i}, {i, i + 1}, {i, i −1}} are open. The union of the open sets {{2,3}, {3}, {3,4}} and {{4,5}, {5}, {5,6}} is the open set {{2,3}, {3}, {3,4}, {4,5}, {5}, {5,6}}. The union of the open sets {{i}, {i, i + 1}, {i, i −1}} such that i ≤ 2 or i ≥ 6 is the open set /{{4}}. The complement of this open set is the closed set {{4}}. Let us consider the following sets (i ∈, k ≥ 1):

C_ik = {{i},{i,i + 1},{i + 1}, …, {i + k − 1},{i + k − 1,i + k},{i + k}}

It is easy to see that

The sets {{i}, {i, i + 1}, {i, i −1}}, and {{i, i + 1}} (i ∈ are a countable basis of) are a countable basis of . M = {{i}, {i + 1}, {i, i + 1}}, which is neither open nor closed in , has the following inherited topology,

G_M = {ø,{{i,i + 1}},{{i},{i,i + 1}},{{i + 1},{i,i + 1}},M}

in which the closed sets are as follows:

{ø,{{i}},{{i + 1}},{{i},{i + 1}},M}

Thus M is connected, because it is not a union of two disjoint nonempty closed sets.

6.1.3 Topologies on incidence pseudographs

Let [S,I, dim] be an n-incidence pseudograph. The set of all open subsets of S (consisting of nodes of any dimension) defines a topology on S. Our particular interest is in components that consist of principal nodes. A complete subset M ⊆ S is not always a union of components, because there may be i-nodes in M that are not incident with any n-node in M. M is called purely n-dimensional iff it is a union of components.

Let M be a purely n-dimensional complete subset of S. Then the following is true where the frontier ∂M and interior M° are defined by the topology G of Theorem 6.1:

If M is closed, we also have M = M^•.

6.2.1 General definition

[S, G] is called a digital topology in the grid cell model iff and G is a family of open sets that satisfies T1 through T3, as well as the following:

(A singleton is a set of cardinality 1.) These properties exclude, for example, the degenerate topology , in which every set that contains at least two pixels is disconnected.

In the grid point model, let d be a metric on (n ≥ 1), and let A_d(p) = {q : q ∈ ∧ d(p,q) = 1}. A subset of is called connected with respect to d iff it is connected with respect to the adjacency relation A_d. [, G] is called a digital topology in the grid point model if S = (n ≥ 1), and G is a family of open sets that satisfies T1 through T3, as well as the following:

It can be shown that, in the 2D grid point space, D1 and D2 imply D3.

6.2.2 The grid point topology

Let p = (x₁,…, x_n) ∈ (n ≥ 1), and let η₁ (p) be the smallest nontrivial neighborhood of p with respect to the Minkowski metric L₁ on (see Section 3.2.2). Define the following:

We call p an odd (even) grid point if x₁ + …. + x_n is odd (even). Note that the relation U_GP is asymmetric on .

{U_gp (p): p ∈ } is a countable basis of a topology that we call the grid point topology [, U_GP]. For example, for n = 1, this basis consists of the sets {2i + 1} and {2i − 1, 2i, 2i + ≥ 1). This topology is called the alternating topology on . It is sketched in Figure 6.1.

U_GP defines an adjacency relation A_GP on : p,q ∈ A_GP iff p∉q and p ∈ U_GP(q) or q ∈ U_GP(p). It is not hard to see that A_GP = A₄ if n = 2 (see Figure 6.2) and A_GP = A₆ if n = 3. This topology is an Aleksandrov space and a T₀-space.

Open and closed sets, the interior and closure of a set, and the frontier of a set (the difference between its closure and its interior) can all be defined in the grid point topology. For example, any set that contains an even grid point and at most three of its 4-neighbors (which are odd grid points) is not open, and any set that contains only even grid points is closed.

Figure 6.3 shows two embeddings of the 2D grid point topology into the plane for which the odd grid points map onto the pixel positions in a regular orthogonal grid. Figure 6.4 is based on the embedding shown on the left in Figure 6.3. It shows on the left the two possible configurations of the smallest neighborhood of an even grid point and on the right an example of a closed set. In accordance with the definition of complete subsets of incidence pseudographs (see Section 5.1.1), we can define complete subsets of in the grid point topology; an even grid point must be in such a subset if its smallest neighborhood is in the subset.

Let d_s be the graph metric defined by a switch state matrix S on (see Section 2.1.3). The relation of s-adjacency defines sets A_s(p) = {q ∈ : d_s(p,q) = 1}. Let the following be true:

The family of sets U_s(p), p ∈ , is not the basis of a topology on . To see this, consider h-adjacency, which is an example of an s-adjacency, and consider two “diagonally adjacent” even grid points p and q. U_s(p) ∩ U_s(q) contains exactly four grid points and so is not one of the sets U_s (p). If r is another even grid point “diagonally adjacent” to p, we have U_s(p) ∩ U_s(q) ∩ U_s(r) = {p}. It follows that all subsets of are open, so the family of sets U_s(p) is a basis for the degenerate topology in which only singletons are connected.

6.2.3 The grid cell topology

The incidence grid [, I, dim](n ≥ 1) defines a poset [, ≤] such that the following is true for all c₁, c₂ ∈ :

c₁ ≤ c₂ iff c₁ ∈ I(c₂) ∧ dim(c₁) ≤ dim(c₂)

The poset topology on [, ≤] is called the grid cell topology. This topology is a T₀-space, because it is defined by a partial order. A complete purely n-dimensional subset of is topologically connected in this topology iff it is connected for the adjacency relation in Definition 5.3. We will see at the end of this section that [, ≤] is a digital topology.

The star of a cell c is the set of all cells c^′ ≥ c; it is the smallest neighborhood of c in the grid cell topology. Figure 6.5 shows examples of stars. The stars are a countable basis of the grid cell topology.

The 2D grid cell topology [, ≤] defines a partition of the plane into grid cells, grid edges, and grid vertices. Figure 2.3 (left) shows a graphic sketch and Figure 2.13 the geometric realization of the 2D incidence grid used throughout this book. P.S. Aleksandrov and H. Hopf used this 2D example in 1935 to illustrate the poset topology.

The following is another way of defining a topology on . We begin by partitioning into a countable number of pairwise disjoint intervals. This partition defines a one-to-one mapping such that, for each i ∈ , f⁻¹(i)is a connected subset of with respect to the Euclidean topology. We then use the Euclidean topology on to induce a topology on based on these intervals. A subset M of is open in this topology iff f⁻¹(M) is open in the Euclidean topology on .

The topology induced on in this way may not be of interest. For example, let f (x) be the integer nearest to x; if x is a half-integer i + ½, let f (x) = i. Then f⁻¹(i) = (i − 2, i + 2) for all i ∈ (i.e., f⁻¹(i) is neither open nor closed in ), and the same is true if we take f (i + ½) = i + 1. As a result, no proper subset of can be open or closed (i.e., the induced topology on is the trivial topology that has only the empty setø and itself as open and closed sets). However, we have the following:

For example, the 2D Euclidean topology is the product of two one-dimensional Euclidean topologies. The topologies on defined previously can be used to define product topologies on (n ≥ 2). A product of two Aleksandrov topologies is Aleksandrov, and the corresponding partial order is the product of the two partial orders.

The alternating topology is an Aleksandrov space, and so are finite products of alternating topologies. Let U_GC(p) be the smallest neighborhood of p ∈ in such a product topology. (We use the subscript “GC,” because this discussion will lead us back to the grid cell topology.)

Figure 6.6 shows the asymmetric neighborhood relation U_GC in the product of two alternating topologies on .

M ⊆ is open in the product of two alternating topologies iff the following is open in , where f is as it is in Example 6.2:

(6.3)

Figure 6.7 shows an embedding of this 2D product topology into the plane such that all grid points {(2i + 1,2j + 1)} (shown as squares) are in pixel positions. Figure 6.8 shows on the left the smallest neighborhoods of grid points (compare Figure 6.5) and on the right an example of a closed set. The smallest neighborhood of a grid point (2i + 1, 2j + 1) contains only that point; the smallest neighborhood of a grid point (2i, 2j) is its 8-neighborhood; and all other grid points have smallest neighborhoods of cardinality 3, arranged either horizontally or vertically.

Products of alternating topologies are T₀-spaces. For example, the neighborhood of a grid point p = (2i + 1, 2j + 1) does not contain any of the grid points that are 8-adjacent to p.

From this and Theorem 6.3, it follows that [, ≤](n ≥ 1) is a digital topology.

6.2.4 The number of digital topologies

There is only one digital topology for n = 1: the alternating topology on .

Let be a digital topology, and let U(p) be the intersection of all of the open sets of G that contain p. Then, for all p ∈ , we must have U (p) ⊆ N₈(p). If not, the 8-disconnected set /A₈ (p) would be connected in , because any open set containing p would also contain a point in /N₈(p).

This result limits the possible topologic neighborhoods U(p) that can be used to define a basis for a digital topology:

It follows that the 2D grid point and grid cell topologies are the only two possible 2D digital topologies.

In addition to the 3D grid point and grid cell topologies, we also have the product of two one-dimensional grid cell topologies and one one-dimensional grid point topology; a topology in which alternate grid planes have the grid point and grid cell topologies; and a topology with open sets that are the closed sets of .

The grid point and grid cell topologies exist on for all n; they are the “most regular” digital topologies.

Geometric realizations such as those shown in Figures 2.13 and 2.14 are models for the 2D and 3D grid cell topologies; these models can be generalized to n dimensions.³ The grid point topology can also be geometrically represented by a tessellation of the Euclidean plane or space into convex polygons or polyhedra. For example, in Figure 6.10, the squares represent odd grid points (2-cells), and the trapezoids represent even grid points (1-cells); there are no 0-cells in this digital topology.

The algorithms described in Section 5.4.1 can be used to assign 1-cells to their adjacent 2-cells that have the largest pixel values.

The values of topologic properties of a set M of pixels or voxels depend in general on which digital topology is being used. These values remain the same if the topologic spaces are homeomorphic (see Definition 6.8) and M is interpreted in the same way (e.g., as an open set).

6.2.5 Topologic adjacency and dimension

The concept of a smallest neighborhood U (p) in an Aleksandrov space allows us to define a symmetric adjacency relation on the space (see Section 2.1.4):

This relation defines an adjacency structure [S, A] that does not necessarily satisfy properties A1 through A3 of an adjacency graph. For example, if S is not topologically connected, then [S, A] does not satisfy A2. The degenerate topology is an Aleksandrov space with U (p) = {p} for all p ∈ S; it generates the degenerate adjacency relation A = ø. Obviously, the adjacency relations Aα defined by the metrics dα (α ∈ {4,6,8,18,26}) are not the same as the adjacency relation A = ø in the degenerate topology induced by the metric spaces (n = 2 or 3). Definition 6.6 relates to Definition 5.2 as follows: let two i-adjacent nodes c₁ and c₂ both be incident with the i-node c, which differs from both c₁ and c₂. In the Aleksandrov space [S, ≤], we have two adjacency pairs {c, c₁} and {c, c₂}, and c₁ and c₂ are connected via c.

The smallest neighborhoods U_GP and U_GC of grid points p ∈ (n ≥ 2) define adjacency relations A_GP and A_GC as in Definition 6.6. A_GP = A₄ in 2D and = A₆ in 3D. A_GC(p) = A₄(p) in 2D iff p has one odd and one even coordinate, and it equals A₈(p) otherwise.

Any adjacency relation on a set S defines paths, connectedness, components, and so forth, as discussed in Sections 1.1.4 and 1.2.5. Let A* (p) be the union of A(p) with all points r ∈ S for which there exist q₁,q₂ ∈ A(p) such that a shortest A-path from q₁ to q₂ not passing through p passes through r. For example, for p ∈ , and and for q ∈ . We have A(c)= A* (c) for any cell c in the grid cell topology.

A set M is called totally disconnected with respect to adjacency A iff there is no pair of distinct points p, q ∈ M such that {p, q} is A-connected.

Figure 6.11 shows examples of one- and two-dimensional sets in the 4- and 8-adjacency grids and in the 2D incidence grid.

Figure 2.20 shows all 4-connected sets of grid points of cardinality 8; the two-dimensional sets (with respect to 4-adjacency) are shown with filled dots.

An elementary grid triangle is a set T = {(i,j), (i + 1, j), (i + j + 1)} or a 90°, 180°, or 270 rotation of it. Such a T is one-dimensional for A₄ in accordance with case (iii).

This proposition can be proved using a case discussion similar to that used in the proof of Proposition 6.2.

In 3D, consider adjacency relation A₆, and let M = N₂₆(o) = A₂₆ (o) ∪{o} where o =(0,0,0). Without using the extended set A* in case (iv), we obtain the following:

For any p ∈ M and L = A₆(p) ∩ M, L is a totally disconnected nonempty set with respect to A₆ so that dim_A(L) = 0 and dim_A(M) = 1.

Using the extended set A* in Definition 6.7 makes M 3D for A₆, A₁₈, and A₂₆. For example, for o ∈ M and L = A₁₈(o) ∩ M, we have card(A₁₈(q) ∩ L) ≥ 4 for any q ∈ L; for example, card(A₁₈(q) ∩ L) = 4 for q =(0,0,1), and card(A₁₈(q) ∩ L) = 6 for q =(1,0,1). By repeated application of case (iv), we obtain the following:

For any p ∈ A₁₈(q) ∩ L, we have dim_A(A₁₈(p) ∩ (A₁₈(q) ∩ L)) = 0 using case (ii); hence dim_A(A₁₈(q) ∩ L)= 1, dimA(L)= 2, and dim_A(M)= 3.

Note that the dimensions of cells in incidence grids are the dimensions of subsets of and that the Euclidean topology is not an Aleksandrov space. For example, the countably infinite intersection of the open intervals (−ε, +ε), for all rational ε such that 1 ≥ε> 0, is the closed singleton {0}.

6.3.1 Homeomorphy

Let Φ be a mapping of a topologic space S₁ into a topologic space S₂. Φ is called continuous iff, for any open subset M of S₂, the set Φ⁻¹(M) = {p ∈ S₁ : Φ(p) ∈ M} is open in S₁.

Two topologic spaces are called homeomorphic or topologically equivalent iff each of them can be mapped by a homeomorphism onto the other.

Two spaces can be homeomorphic only if they have the same cardinality, because a homeomorphism is one-to-one.

The Euclidean plane is homeomorphic to an open halfsphere. In fact, the gnomonic azimuthal projection (perspective projection from the center of the halfsphere onto a plane tangent to the halfsphere) defines a homeomorphism between the halfsphere and the plane; see the left of Figure 6.12. A triangle is homeomorphic to a circle; see the right of Figure 6.12. The surfaces of a sphere, a cube, and a cylinder are pairwise homeomorphic, but they are not homeomorphic to the surface of a torus.

A circle with one point removed is homeomorphic to ; the surface of a sphere with one point removed is homeomorphic to ; and the (hyper)surface of a 4D hypersphere with one point removed is homeomorphic to . A disk with one point on its frontier removed is homeomorphic to a closed halfplane. A sphere (or cube) with one point on its surface removed is homeomorphic to a closed halfspace of . A disk with two points on its frontier removed is homeomorphic to a closed strip between two parallel straight lines in . A compact subset of can be homeomorphic only to a compact subset of ; this suggests that we should use compact subsets as geometric representations of discrete spaces.

Figure 6.13 (left) illustrates in gray two open squares in the Euclidean plane (each of these squares is homeomorphic to the infinite plane) and, in black, the union of two closed squares that have exactly one point in common (this union is homeomorphic to the union of two disks that “touch” each other at exactly one point, but it is not homeomorphic to the unit disk). Figure 6.13 (right) shows only closed subsets of the Euclidean plane: in gray, two large squares (each homeomorphic to the unit disk) and, in black, the union of two large squares, eight elongated rectangles (representing edges of grid squares), and seven small squares (representing vertices of grid squares); this union is also homeomorphic to the unit disk. Evidently, on the right, we have a geometric representation of two open regions and one closed region of the 2D incidence grid.

For example, the property of being the empty set is a topologic invariant, and so is the property of being a nonempty set. Dimension (see Definition 6.7) is a nontrivial example of a topologic invariant. Finding topologic invariants is a central problem in topology. Similarly, calculating topologic invariants is a central problem in digital topology. For example, the number of components is a topologic invariant. Poincaré has shown that the Euler characteristic of a regular tessellation of an n-dimensional space is a topologic invariant; we will discuss this result in Section 6.4.5.

Nonhomeomorphy can be proved by comparing topologic invariants; if two sets have different values of a topologic invariant (e.g., different dimensions), they cannot be homeomorphic.

In Figure 6.13 (left), the two gray squares, which are open in ², are nonhomeomorphic to the union of the two (closed) black squares. In Figure 6.13 (right), each of the two (closed) gray squares is homeomorphic to the union of the black (closed) squares and rectangles.

Note that topologic equivalence between picture regions depends on how marginal cells are assigned to principal cells. For example, the two regions of solid dots shown on the left in Figure 6.14 are homeomorphic in the (4,8)-adjacency grid, and their geometric representations in ² are homeomorphic to the connected set shown on the right. (As we saw in Section 5.4.1, assuming (4,8)-adjacency is equivalent to assuming ordered adjacency with black > white.) For all of these regions, we have χ = 1. Even if we considered the two regions on the left (incorrectly) as graphs (with v = 48, e = 78, and f = 31 on the left and v = 35, e = 37, and f = 3 on the right, counting all faces equally whether they are holes or atomic cycles), we would obtain χ = + 1 in both cases, because these graphs are planar.

6.3.2 Isotopy

Two subsets L and M of a topologic space S are called isotopic iff there exists a homeomorphism Φ from S onto itself such that Φ(L) = M.

Isotopy is a stronger concept than homeomorphy. For example, suppose S contains a circle C and a rectangle R (see Figure 6.15). In the picture on the left, (A) R is surrounded by C, and, in the picture on the right, (B) R is outside of C. The two pictures are not isotopic in S; there exists no homeomorphism of S onto itself that maps (A) into (B).⁴

It can be shown that (A) and (B) are isotopic in ³. The two bands on the left in Figure 6.16 are homeomorphic subsets of ³, but they are not isotopic in ³. The two curves γ₁ (a meridian) and γ₂ (a parallel of latitude) on the surface of the torus shown on the right in Figure 6.16 are isotopic. The curves γ₁ and γ₃ are isotopic in ³ but not on the surface of the torus.

We can think of regions as being characterized by homeomorphy and pictures as being characterized by isotopy. The following definition makes use of the geometric representations defined in Section 2.1.5.

As seen in Section 6.3.1, topologic equivalence between pictures depends on how marginal cells are assigned to principal cells. The two binary pictures in the (4,8)-adjacency grid shown in Figure 6.17 can be made isotopic by changing a few pixel values.

We saw in Theorem 4.2 that a 2D binary picture in the (4,8)- or (8,4)-adjacency grid has a rooted region adjacency tree in which the root represents the infinite background component.

6.3.3 Homotopy

Homotopy allows us to give a precise definition of the topologic structure of a region. In particular, it allows us to define “simply connected.”

To define the notion of homotopy, we must first define the fundamental group of a subset M of a topologic space [S, G]. A continuous function with and defines a parameterized path γ from p to q in M. Two parameterized paths γ₁ and γ₂ in M that have the same endpoints are called homotopic iff γ₁ can be continuously transformed into γ₂ in M. More precisely, let the paths γ₁ and γ₂ be defined by the functions and . A continuous transformation of γ₁ into γ₂ is a continuous function ψ : [0,1] × [0,1] → M such that and for any real x in [0,1]. If γ₂ is a single point,ψ defines a contraction of γ₁ in M into a single point.

Homotopy defines an equivalence relation on the class of all parameterized paths in M. For example, Figure 6.18 shows three paths from p to q in M; γ₁ and γ₂ are homotopic, but γ₃ is not homotopic to γ₁ or γ₂.

Let p₀ ∈ M be the endpoint of γ₁ and the starting point of γ₂. The product is defined by concatenation: and are combined into a single function

This product is compatible with homotopy; if γ₁ is homotopic with γ₃ and γ₂ is homotopic with γ₄, then with .

Let [γ] be the class of all paths homotopic in M to γ with respect to a given point p₀ of γ. The setπ(M) of all of these classes is a group under called the fundamental group of M with respect to p₀. A path that is contractible in M into the single point p₀ is called zero-homotopic. The set of zero-homotopic paths is the identity ε of the groupπ(M) (i.e., for any ξ ∈ Π (M), we have ). If the path γ is defined by φ and the path [γ⁻¹] is defined byψ(x) = φ(1 – x), then [γ⁻¹] is the inverse of . Although is associative, in general it is not commutative (Abelian).

If p₀ and p₁ can be connected by a path in M, the fundamental groups of M with respect to p₀ and p₁ are isomorphic. It follows that, if M is connected, its fundamental group does not depend on p₀. The fundamental group is a topologic invariant in homotopy theory.

This definition is based on work by C. Jordan (1866, on the topologic equivalence of curves) and H. Poincar6 (1892, on the fundamental group).

In other words, M is simply connected iff any parameterized path in M that starts and ends at the same point is contractible in M into a single point. For example, a disk and a ball are both simply connected.

The linear skeleton of a set M ⊆ ⁿ (see Figure 6.19) is defined by continuous contractions; hence a set is homotopic to its linear skeleton.⁵ For example, the linear skeleton of a simply connected set is a point and that of a torus is a simple closed curve.

6.4.1 Geometric complexes and the Euler characteristic

An elementary curve γ (to be defined in Chapter 7) can be partitioned into one-dimensional geometric complexes S that consist of arcs (also called 1-cells) and their endpoints (also called isolated points or 0-cells). Let α₀ be the number of 0-cells in S and α₁ the number of 1-cells in S that contain at least one 0-cell. The difference χ = α₀ –α₁ is called the Euler characteristic of S. We will see in Section 6.4.5 that any partition of the same elementary curve has the same value of χ.

For example, a circle is partitioned by n ≥ 1 vertices into n arcs; hence χ = 0. For a simple arc with two endpoints, we have x = 1. Figure 6.20 shows the linear skeleton of a tetrahedron, which has α₀ = 4 vertices,α₁ = 6 arcs, and x = −2. Adding a vertex on any of the arcs increases α₀ and α₁ by 1 and thus leaves x unchanged.

The connectivity β₁ of a one-dimensional geometric complex S is as follows, where β₀ is the number of components of S :

β₁ = β₀ –α₀ +α₁

β₁ is equal to the number of atomic cycles (sets of components with a union that is a simple curve) of S.β₀ and β₁ are called the first two Betti numbers⁶ of S. (A general definition of Betti numbers will be given in Section 6.4.5.) Figure 6.21 shows an example with four 0-cells, six 1-cells, two components, and four atomic cycles.

A planar drawing of a one-dimensional geometric complex (see Figure 6.20 [right] and Figure 6.21) can be regarded as a planar-oriented adjacency graph in which we assume clockwise local circular orders at the nodes. This graph has Euler characteristic χ = β₀ = α₀ –α₁ +α₂. It follows that β₁ = α₂ (the number of faces of the graph) is equal to the total number of cycles minus the number of outer cycles, each of which defines the border of a component.

A 2D geometric complex, as introduced by J.B. Listing in 1861, contains a finite number of bounded closed subsets of ², which may be faces, curves, arcs, or isolated points (e.g., endpoints of arcs). The complement of the union of all of these compact sets is an open set called the unbounded exterior.

For example, the frontier (surface) of a simple polyhedron in ³ can be partitioned into elements of a 2D geometric complex called a surface complex of the polyhedron. A single face can be represented by a simple polygon, its edges, and its vertices (the endpoints of the edges). The surface of a simple polyhedron is topologically equivalent to the surface of a sphere. The unbounded exterior of this 2D complex splits into two disjoint open sets (see the separation theorems in Section 7.4), one bounded (the interior of the polyhedron), and the other unbounded. Let α₀,α₁, and α₂ be the number of vertices, edges, and faces of a simple polyhedron. The Descartes-Euler polyhedron theorem (see Equation 4.5)α₀ –α₁ +α₂ = 2 was originally established (by Descartes and Euler) only for convex polyhedra in 3D space, but it is correct for any simple polyhedron.

In 1813, A. Cauchy generalized the Descartes-Euler polyhedron theorem (see Equation 4.5) by introducing intercellular faces into the polyhedron. This results in the following,

(6.4)

where α₃ is the number of polyhedral cells; see Figure 6.23 (left). Cauchy considered only convex polyhedra.

In 1812, A.-J. Lhuilier suggested a generalization that also allowed “tunnels” and “bubbles.” He claimed that the following was true,

(6.5)

where b is the number of bubbles, t the number of tunnels, and p the number of polygons (“exits of tunnels”) on faces of the polyhedron. His discussion of the number of tunnels did not cover the full range of possibilities. For example, Figure 6.19 illustrates the difficulty of defining a tunnel; in fact, an object such as a sponge can have a “network” of tunnels. Numbers of cavities (bubbles) and tunnels will be discussed further in Section 6.4.5.

3D geometric complexes are used to model partitions of 3D sets into convex polyhedra or simplexes. A partition must be “complete” (e.g., if a polyhedron is in the complex, its surface complex must also be in the complex). The object in Figure 6.19 is a 3D geometric complex that has α₀ = 88 vertices,α₁ = 132 edges,α₂ = 36 faces (assuming a straightforward partition of the surface into a surface complex), and one solid cell (α₃ = 1). The Euler characteristic of the 2D surface complex is χ = α₀ –α₁ +α₂ = −8 (regarding the object as a hollow surface), and that of the 3D object is χ = α₀ –α₁ +α₂ –α₃ = −9.

6.4.2 Euclidean complexes

The geometric complexes discussed so far are Euclidean complexes, which are partitions into compact convex sets. As a default, we assume that these sets are convex polyhedra. Surface complexes will be defined in Chapter 7.

The notion of dimension plays an important role in the definition of complexes. Dimension allows us to distinguish isolated points from line (or arc) segments and edges from faces. (In a vector space, the dimension of a set is the greatest number of linearly independent vectors in the set, but this is not a topologic characterization.)

Let C ⊂ ⁿ be a convex polyhedron and let P be an m-dimensional subspace (m <n) of ⁿ. P ∩ C is called an (n − 1)-side of C if dim(P ∩ C) = n − 1. A nonempty intersection of finitely many (n − 1)-sides is called a proper side; if it has dimension k, it is called a k-side. Every (n − 2)-side is a side of exactly two (n − 1)-sides. The 0-sides of C are its vertices. C is an improper side of itself. If C is bounded, it is called a convex cell.

Let M ⊆ ⁿ be the union of a finite number of convex cells. A Euclidean complex is a partition S of M into a nonempty finite set of convex cells that has the following properties:

The union of the cells of S need not be connected, and a subset of the cells of S need not define a Euclidean complex.

Figure 6.24 shows four partitions of a (nonsimply connected) polygon. For the partition into squares on the left, we have α₀ = 106,α₁ = 165, and α₂ = 59 (not counting the hole); for the partition into triangles on the right, we have α₀ = 106,α₁ = 224, and α₂ = 118. Both counts result in x = 0. Grid cell complexes formed by cells in are examples of Euclidean complexes. The partition on the left in Figure 6.24 is a 2D grid cell complex, and the partition on the right is a triangulation (see Section 6.4.3). For the partitions in the middle (where we also count the hole as a face), we have α₀ = 59,α₁ = 76, and α₂ = 18 and α₀ = 61,α₁ = 79, and α₂ = 19 so that χ = 1.

Figure 6.25 shows the 1-component illustrated in Figure 6.24 (in the grid point model), as well as another 1-component. The 1-component on the left has 12 atomic cycles, one inner border cycle, and one outer border cycle (i.e.,α₂ = 14,α₁ = 71, and α₀ = 59) so that x = α₀ − α₁ + (α₂ − 1) = 1. The single inner border cycle defines a hole; it is not counted in the Euler characteristic of the Euclidean complex, so χ = 0 for the complex. The second 1-component has the same values of χ (0 for the Euclidean complex and 1 for the oriented adjacency graph); the two 1-components are homeomorphic (see Definition 6.10). Note that the adjacency graphs of the components are different; the graph of the component on the left is not 2-strong, but the graph of the other component is 2-strong.

6.4.3 Simplicial complexes; triangulations

A Euclidean complex is called simplicial iff all of its cells are simplexes. An n-dimensional simplex (n-simplex) is the convex hull of n + 1 vertices p₀, p₁,…, p_n, where the vectors are linearly independent. For example, a 3-simplex is a solid tetrahedron. Complexes with cells that are tetrahedra are of special interest for modeling the boundaries of 3D isothetic grid polyhedra [476].

A finite Euclidean complex that contains only triangles, line segments, and points is called a triangulation; evidently, such a complex is simplicial. The frontier of any polyhedron can be triangulated.

Figure 6.26 shows three examples of triangulations. We will now illustrate how polyhedral surfaces can be constructed by identifying vertices in the triangulation on the right. If we identify P₅, P₈, P₁₁, and P₁₄ (the four corners of the large square), the (directed) line segment P₅P₁₄ becomes identified with (“glued to”) the directed line segment P₈P₁₁, as does P₅P₈ with P₁₄P₁₁. If we then identify P₆ with P₁₃, P₇ with P₁₂, P₉ with P₁₆, and P₁₀ with P₁₅, it can be shown that the resulting triangulation is homeomorphic to the surface of a torus. If instead we identify P₆ with P₁₂, P₇ with P₁₃, P₉ with P₁₆, and P₁₀ with P₁₅, the resulting triangulation is homeomorphic to a Klein bottle.

If we identify vertices P₁,P₂,P₃, P₄, P₁₇, P₁₈, and P₁₉; P₅ and P₁₁; P₆ and P₁₂; P₇ and P₁₃; P₈ and P₁₄; P₉ and P₁₅; and P₁₀ and P₁₆, we have a triangulation of the projective plane (P.S. Aleksandrov, 1956). These examples can serve as a warning not to underestimate the complexity of triangulations, even if they have small cardinalities. A triangulation used in a surface analysis algorithm (in 3D picture analysis) should certainly not contain a Klein bottle or a projective plane!

Any polyhedral surface is compact. The frontier of a simple polygon (as defined in Section 1.2.2) is an example of the union of a one-dimensional triangulation; it too can be regarded as a polyhedral surface.

The dimension of a triangulation is the maximum dimension of its elements. A 2D triangulation T is called pure iff every point or line segment in T precedes some triangle in T with respect to the side-of relation. The surface of a simple polyhedron is the union of a pure 2D triangulation.

A path of sets(M₁,M₂,…,M_n) is a finite sequence of sets such that M_i ∩ M_i+1 1 ≠ø (i = 1,…, n−1). Such a path connects M₁ with M_n. A polygonal path is a path of line segments. A pure 2D triangulation T is called strongly connected iff every two triangles T₁ and T₂ in T are connected by a path of triangles, all of which are in T. The surface of a simple polyhedron is a strongly connected triangulation. The analysis of simple polygons and simple polyhedra is often done with the aid of triangulations.

6.4.4 Abstract complexes

The theory of finite abstract complexes is based on a partial ordering that generalizes a reflexive, transitive, antisymmetric “bounded-by” relation rather than the reflexive, symmetric, and in general nontransitive incidence relation.

Let S be a finite or countably infinite set of points. Assign a nonnegative integer dim(c), which is called the dimension of c, to each c ∈ S. The following definition goes back to the axiomatic definition of geometric complexes by E. Steinitz in 1908 and to the topologic study of abstract complexes by A.W. Tucker in 1933. An abstract complex [S, ≤, dim] has two properties:

An abstract complex is an example of a poset topology. The elements of S are called the cells of the complex. The study of abstract complexes does not depend on interpreting cells as vertices, edges, faces, and so forth. Any subset of an abstract complex is also an abstract complex and defines a topologic subspace of the complex.

If dim(c) = i, we call c an i-cell. The index dimension of an abstract complex is n iff dim(c) ≤ n for all c ∈ S and dim(c) = n for at least one c ∈ S.

The “side-of” relation in a Euclidean complex is an example of the relation ≤ and has property C2. If c₁ ≤ c₂ and c₁ ≠ c₂, we say that c₁ is a proper side of c₂. Two cells are incident iff c₁ ≤ c₂ or c₂ ≤ c₁.

Let [S,I, dim] be an incidence pseudograph. We say that c < c’ if c′ ∈ I(c), c ≠ c′, and dim(c) < dim(c′). If we define c ≤ c′ iff c < c′ or c = c′, [S, ≤, dim] is an abstract complex. Thus our discussion about incidence pseudographs in Chapter 5 can be translated into a language of abstract complexes.

6.4.5 The Poincaré formula

We conclude this chapter with a brief treatment of homology theory. Polyhedra are characterized in combinatorial topology by homology (which is easier to define than homotopy), homology groups, and Betti numbers. The Poincaré formula⁷ describes the Euler characteristic of a partition of a polyhedron (a complex) by its Betti numbers. This provides a general proof that Euler characteristics are topologic invariants. A precise statement of the Poincaré formula requires a brief introduction to homology theory.

Let [S, ≤, dim] be a Euclidean complex. We write c ∈ S as c⁽ⁱ⁾ if dim(c) = i. In Section 5.2.1, we defined i-chains in S as expressions of the form where b_k = 0 or 1, and the sum is over all i-dimensional cells in S. We recall that i-chains can be added modulo 2. We say that is in C⁽ⁱ⁾ iff b_k = 1, and we write C⁽ⁱ⁾ = 0 if every b_k is 0. Let ∪ C⁽ⁱ⁾ be the union of the cells in C⁽ⁱ⁾. Evidently, C⁽ⁱ⁾ = 0 iff ∪ C⁽⁰⁾ = φ.

In Section 5.2.1, we defined the frontier of an i-chain , and, if i> 0, is the (i − 1)-chain where a_k is the number of i-cells in C⁽ⁱ⁾ that are incident with . C⁽ⁱ⁾ is called an i-cycle if . Any 0-chain is a 0-cycle, and the frontier of any chain is a cycle, because .

We write the following if there is an i-chain C⁽ⁱ⁾ such that C⁽ⁱ⁻¹⁾ ∼0

We write C⁽ⁱ⁾ ∼ C′⁽ⁱ⁾ iff C⁽ⁱ⁾ + C′⁽ⁱ⁾ ∼ 0. Evidently, ∼ is an equivalence relation; it is called a homology.

Let K =[S, ≤, dim] be a Euclidean complex with index dimension n. A set B of i-cycles of k is called a basis for the i-cycles of K with respect to homology if every i-cycle C⁽ⁱ⁾ of K is homologous to a sum of i-cycles of B; in essence, there are coefficients a_k such that the following imply b_k = 0 (modulo 2) for all k:

and

The cardinality β_i of a basis for the cycles of K is called the ith Betti number of K.

This theorem was originally proved by H. Poincaré only for n = 2 (i.e., for 2D manifolds [surfaces] in 3D Euclidean space).

The Euler characteristic is defined by the following where α_i is the number of i-cells in K:

Theorem 6.8 through 6.9 imply the following:

Let K be a bounded 3D set that consists of several connected components and with a surface that consists of several orientable closed surfaces. For this K, β₀ is the number of connected components,β₁/2 is the number of tunnels, and β₀ +β₂ is the number of closed surfaces (so that there are β₂ cavities).

Let K be the edge skeleton (a one-dimensional complex) of a tetrahedron; it has v = 4 vertices, e = 6 edges, and f = 0s faces. Here we have β₀ = 1,β₁ = 3 (note that the 1-cycle around each triangle is the sum of the three 1-cycles around the other three triangles), and β₂ = 0 so that χ = −2. Note that we do not have “1.5 tunnels” in this case; the edge skeleton is not a surface. For one-dimensional complexes in 3D space,β₀ is the number of components, and β₁ is the number of tunnels. A one-dimensional complex in the plane has β₁ holes (the 2D analog of tunnels). Note that a Euclidean one-dimensional complex is always a planar graph (i.e., faces are not counted in its Euler characteristic, because it is only one-dimensional), and β₁ is its number of internal faces, excluding the unbounded external face; see Figure 6.28. Oriented adjacency graphs allow us to generalize the Euler characteristic and not be limited to planar graphs. See Section 17.5 about tunnel-free subsets of G_m,n,l.

6.4.6 Homology groups

Betti numbers can also be defined using homology groups. Let [G, +, 0] be an additive abelian group with identity 0. [H, +, 0] is called a subgroup of [G, +, 0] iff H ⊆ G and f,g ∈ H imply f – g ∈ H. A homomorphism φ from [G, +, 0] onto [H, +, 0] is a function from G onto H such that φ(f) –φ(g) = φ(f – g) for all f, g ∈ G. If φ is one-to-one, it is called an isomorphism. If φ is a homomorphism, H = φ⁻¹(0) is a subgroup of G called the kernel of φ. The kernel of an isomorphism is the singleton {0}.

Let H be a subgroup of G and f ∈G. f_H = {f + g : g ∈ H} is called a coset of G relative to H. Note that two cosets are either disjoint or identical. The set of cosets of G relative to H is an additive group called the factor group G/H of G modulo H; we define f_H + g_H = (f + g)_H.φ : G → G/H is a homomorphism and H is its kernel.

The set C⁽ⁱ⁾ of i-chains of a Euclidean complex K is an abelian group under addition modulo 2. Let G⁽ⁱ⁾ be the subgroup of C⁽ⁱ⁾ that consists of all i-cycles, and let F⁽ⁱ⁾ be the subgroup of G⁽ⁱⁱ⁾ that consists of all frontiers ϑC_(i+1) of (i + 1)-chains. The factor group H⁽ⁱ⁾= G⁽ⁱ⁾/F⁽ⁱ⁾ is called the i-th homology group (Betti group) of K. The homology ∼ partitions the cycles G⁽ⁱ⁾ into equivalence classes called homology classes. It can be shown that the dimension of H⁽ⁱ⁾ is the i-th Betti number.

Example 6.3 showed that the surface of a torus and a planar drawing of an 8 have different fundamental groups (i.e., they are not identical with respect to homotopy). On the other hand, the homology groups of both of these sets are isomorphic to the direct sum [, +, 0] [, +, 0]. Thus isomorphism of homology groups does not imply homotopy (isomorphism of fundamental groups).

1. Does the adjacency grid have a topology in which 1-connectedness is the same as topologic connectedness?

2. Describe the Aleksandrov topology of the poset [, ≤].

3. Explain why the product of one one-dimensional grid cell topology and two one-dimensional grid point topologies is already contained in the set of 3D digital topologies listed after Theorem 6.6.

4.  Show that the Euler characteristic χ(Π) of a polyhedron Π ⊂ ³ can also be defined by the following axioms:

(Hint: Prove that χ(Π) is equal to the alternating sum α₀ –α₁ +α₂ where α₀ is the number of vertices,α₁ the number of edges, and α₂ the number of triangles in any triangulation of Π’s frontier.)

5. Prove that, for any (planar) polyhedron Π ⊂ ²,χ(Π) is equal to the number of components of Π (in the Euclidean topology) minus the number of holes in Π.

6. Let n_i be the number of 2× 2 patterns of pixels in a binary picture P that contain exactly i 1s (i = 0,1,2,3,4), and let n_D be the number of such patterns that contain two diagonally adjacent 1s. Let the following be true:

    E_8,4(P) = (n₁ – n₃ – 2n_D)/4 and E₄,₈(P) = (n₁ – n₃ + 2n_D)/4

    The geometric realization of the 2D grid cell topology based on the label order “0 < 1” or “1 < 0” maps the union of the 1s in P into a (planar) polyhedron Π. Prove that χ(Π) = E₈,₄(P) for label order “0 < 1” and that χ(Π) = E_4,8(P) for label order “1 < 0” (see Figure 17.2 for an example).

7. Prove that any convex set in ⁿ (e.g., a single point, a straight line segment, a sphere, a convex polyhedron) is simply connected (i.e., its fundamental group is {ε }).

8. Prove that the free cyclic group is the fundamental group of the annulus and also of ²/{p}, where p is any point in ².

9. Prove that α₀ –α₁ = 1 for any tree (i.e., that the Euler characteristic of any tree is 1).

10. We have given finite and countable examples of abstract complexes. The following is a noncountable example: Let S = {s_a : a ∈ [0,1]} be a noncountable set of abstract cells defined on the real index interval [0,1], where s_a ≠ s_b iff a ≠ b. For a ∈ [0,1], let a = 0 and a₁a₂a₃ … where a_i∈ {0,1,…,9}. Let s_a ≤ s_b iff a = b or a₁ < b₁ and a_i = b_i for all i ≥ 11. Let dim(s_a) = a₁. Show that [S, ≤, dim] is an abstract complex.

11.  Calculate the Betti numbers of the following three tilings (2D complexes):

12. Suppose deletion of all of the invalid edges in a picture leads to the nonconnected undirected graph shown below. Regard each pixel as the centroid of an isothetic unit square, and take the union of all of the squares that correspond to pixels in the same 4-component. The frontiers of the resulting sets are isothetic simple curves. Find the Betti numbers β_i of these sets (i = 0,1,2).

13. Calculate the number of tunnels in the one-dimensional complex that consists of the vertices and edges of a tetrahedron.

14. Consider three “systems of pathways” in a solid sphere: (1) n ≥ 3 straight pathways that start at the surface of the sphere and meet at its center; (2) four pathways that form a hollow tetrahedron inside the sphere, with an exit to the surface of the sphere, at each vertex of the tetrahedron; and (3) a pathway that forms a hollow torus inside the sphere, with n ≥ 1 exits to the surface of the sphere. What are the numbers of tunnels in these three cases?

15. The Arens-Fort space is defined on the (countable) set S = ² by a set G that is the union of ²/{(0,0)} and the family of all sets U ⊂ ² with projections {n :(m, n) ∈ U} that are finite for all but finitely many m ∈ n. Show that [S, G] is a topologic space and does not have a countable basis.

16. Let M ⊆ be closed iff either 1 ∈ M or ∑_n∈M1/n is finite (note that this excludes 0 ∈ M). Show that this defines a topologic space on n that does not have a countable basis for the neighborhoods of 1.