SectionApplications of Products of Topological Spaces
Computers represent information from the real world digitally. That is, a computer screen consists of discrete pixels that are used to mimic the continuous information from the real world. So we exist in \(\R^3\text{,}\) but a computer screen represents information in \(\Z^2\) as illustrated in Figure 20.10. It is important to be able to accurately mimic the continuous information from digital data. One of the key ideas is to have a digital version of the Jordan curve theorem which states that a Jordan curve (a continuous loop that does not intersect itself) in the Euclidean plane separates the remainder of the plane into two connected components (the inside and the outside of the curve). Additionally, if a single point is removed from a Jordan curve, the remainder of the plane becomes connected. The reason a digital Jordan curve theorem is important is that it is only necessary to save the Jordan curves which determine regions, along with the associated colors of the regions, rather than having to save the color of every single pixel in an image.
Figure20.10.Left: The digital plane. Middle: \(4\)-neighbors of a point. Right: \(8\)-neighbors of a point.
A natural start to building a digital topology might be to identify neighborhoods. The idea of a neighborhood is to consider elements that are close to a point, and in the digital world there are different ways to do this. Given a point \((x,y)\) in \(\Z^2\text{,}\) the 4-neighbors of \((x,y)\) are the points vertically or horizontally adjacent to \((x,y)\text{:}\) that is, the points \((x \pm 1, y)\) and \((x, y \pm 1)\text{.}\) The 8-neighbors of \((x,y)\) are the 4-neighbors along with the points diagonally adjacent to \((x,y)\text{:}\) that is, \((x \pm 1, y)\text{,}\)\((x, y \pm 1)\text{,}\)\((x \pm 1, y \pm 1)\text{.}\) These neighbors are illustrated in Figure 20.10, with the crosses indicating the neighbors of the highlighted point.
In the continuous case, we define a path between points to be a continuous function from \([0,1]\) to the space. However, we cannot have continuity in the digital world. So we define paths by moving through neighbor points. That is, if \(k\) is either \(4\) or \(8\text{,}\) a \(k\)-path is a finite sequence \(p_0\text{,}\)\(p_1\text{,}\)\(\ldots\text{,}\)\(p_m\) in \(\Z^2\) such that \(p_1\) is a \(k\)-neighbor of \(p_2\text{,}\)\(p_2\) is a \(k\)-neighbor of \(p_3\text{,}\)\(\ldots\text{,}\) and \(p_{m-1}\) is a \(k\)-neighbor of \(p_m\text{.}\)
Activity20.9.
(a)
Show that there is a \(4\)-path connecting any two points in \(\Z^2\text{.}\) Then explain why there is an \(8\)-path connecting any two points in \(\Z^2\text{.}\)
(b)
In the continuous case, every Jordan curve separates \(\R^2\) into two connected regions. To have a similar theorem in the discrete case, we need a notion of connectedness in \(\Z^2\text{.}\) Every image is made up of a finite number of pixels, and so we can think of a digital image as existing in a finite subspace of \(\Z^2\text{.}\) Since connectedness and path connectedness are equivalent in finite topological spaces, we us the idea of \(k\)-paths to define connectedness in \(\Z^2\text{.}\) We say that a subset \(S\) of \(\Z^2\) is \(k-connected\) if if any two of its points can be joined by a \(k\)-path in \(S\text{.}\)Figure 20.11 show two sets (curves) in the digital plane indicated by the points that connect the line segments (examples taken from A Topological Approach to Digital Topology, T. Yung Kong, R. Kopperman, and P. Meyer, American Mathematical Monthly, 98 (1991), no. 10, 901-917). Let \(S_1\) be the set illustrated at left in Figure 20.11 and \(S_2\) the set at right.
Figure20.11.Sets \(S_1\) (left) and \(S_2\) (right) in the digital plane.
Is \(S_1\)\(4\) connected? Is \(S_1\)\(8\) connected? Verify your answer. Repeat with \(S_2\text{.}\)
(c)
We can now define a Jordan \(k\)-curve to be a finite \(k\)-connected set which contains exactly two \(k\)-neighbors for each of its points. Is \(S_1\) a Jordan \(4\)-curve? Is \(S_1\) a Jordan \(8\)-curve? Verify your answer. Repeat with \(S_2\text{.}\)
(d)
As usual, we define a component to be a maximal connected set. Explain why \(S_1\) is a Jordan \(8\)-curve whose complement is connected and why \(S_2\) is a Jordan \(4\)-curve whose complement consists of three connected \(4\)-components. This example shows that there is no Jordan curve theorem in digital topology using the standard notions of \(k\)-connectedness with \(k\) either \(4\) or \(8\text{.}\) So neither 4-adjacency nor 8-adjacency provides an analogue of the Jordan curve theorem and it is necessary to use a combination of both. That is, a Jordan \(4\)-curve with at least five points separates \(\Z^2\) into exactly two \(8\)-components, and a Jordan \(8\)-curve with at least five points separates \(\Z^2\) into exactly two \(4\)-components.
In Activity 20.9 we discussed the importance of a digital Jordan curve theorem. In the next activity we describe a topology in which such a theorem exists.
Activity20.10.
Consider \(Z\) with the topology \(\tau_1\) with basis \(\{B(n)\}\text{,}\) where
\begin{equation*}
B(n) = \begin{cases}\{n\} \amp \text{ if \(n\) is odd } , \\ \{n-1,n,n+1\} \amp \text{ if \(n\) is even } . \end{cases}
\end{equation*}
This topology is called the digital line topology or the Khalimsky topology on \(\Z\text{.}\) Notice that all sets of the form \(\{n\}\) are open when \(n\) is odd.
(a)
Show that any set of the form \(\{n\}\) where \(n\) is even is closed in the digital line topology.
(b)
To define a Khalimsky topology on \(\Z^2\) we use the product topology. Explain why the collection of sets \(\{B(m,n)\}\) where
\begin{equation*}
B(m,n) = \begin{cases}\{(m,n)\} \amp m \text{ and } n \text{ odd, } \\ \{(m-i,n-j) \mid -1 \leq i \leq 1, -1 \leq j \leq 1\} \amp m \text{ and } n \text{ even, } \\ \{(m,n-1), (m,n), (m,n+1)\} \amp m \text{ odd and } n \text{ even, } \\ \{(m-1,n), (m,n), (m+1,n)\} \amp m \text{ even and } n \text{ odd } \end{cases}
\end{equation*}
is a basis for the Khalimsky topology \(\tau_2\) on \(\Z^2\text{.}\) (This topology was originally published by E. Khalimsky in Applications of connected ordered topological spaces in topology, Conference of math. departments of Povolsia, 1970.)
(c)
Now we want to define a digital Jordan curve. Our first step is to define a digital path. Recall that a path in a topological space is a homeomorphism from the interval \([0,1]\) into the space. So we need the concept of a digital interval. If \(z_1 \lt z_2\) in \((\Z, \tau_1)\text{,}\) the digital interval \([z_1,z_2]\) is the set
Show that \(S_1\) is not a digital path but \(S_2\) and \(S_3\) are digital paths.
(d)
To produce a digital Jordan Curve Theorem, we need a definition of a digital Jordan curve.
Definition20.13.
A digital Jordan curve is a finite connected set \(J\) with \(|J| \geq 4\) such that \(J \setminus \{j\}\) is a digital arc for each \(j \in J\text{.}\)
So every digital Jordan curve is a connected set. Show that any finite digital path in \(\Z^2\) is a connected set.
The upshot of all of this is the following theorem (a proof can be found in A Topological Approach to Digital Topology, T. Yung Kong, R. Kopperman, and P. Meyer, American Mathematical Monthly, 98 (1991), no. 10, 901-917).
Theorem20.14.
If \(J\) is a digital Jordan curve in the digital plane \(\Z^2\text{,}\) then \(\Z^2 \setminus J\) has exactly two components.
The two components in Theorem 20.14 split the digital plane into an infinite region (the outside) and a finite region (the inside).
Show that \(S_2\) is a digital Jordan curve (and thus splits \(\Z^2\) into two connected components).
Digital Jordan curves, as described in Activity 20.10, are important in order to have a digital Jordan curve theorem. Christer O. Kiselman presents the following theorem to characterize digital Jordan curves in Discrete Geometry for Computer Imagery, Springer-Verlag, 2000, p. 46-56.
Theorem20.15.
A subset \(J\) of \(\Z^2\) equipped with the Khalimsky topology is a digital Jordan curve if and only if \(J = \{P_1, P_2, \ldots, P_m\}\) for some even integer \(m \geq 4\) and for all \(j\text{,}\)\(P_{j?1}\) and \(P_{j+1}\) and no other points are adjacent to \(P_j\text{;}\) moreover each path consisting of three consecutive points \(P_{i?1}\text{,}\)\(P_i\text{,}\)\(P_{i+1}\) turns at \(P_i\) by \(45^{\circ}\) or \(90^{\circ}\) or not at all if \(P_i\) is a pure point, and goes straight ahead if \(P_i\) is mixed.
We investigate this theorem in the next activity.
Activity20.11.
(a)
We need to first define the appropriate terms. Let \(X\) be a topological space. Two points \(x\) and \(y\) in \(X\) are adjacent if \(x \neq y\) and the set \(\{x, y\}\) is connected. Then let \(N(x)\) to be the intersection of all neighborhoods of \(x\text{.}\) Show that distinct elements \(x\) and \(y\) in a topological space \(X\) are adjacent if and only if \(x \in N(y)\) or \(y \in N(x)\text{.}\)
(b)
A point \((x_1,x_2)\) in \(\Z^2\) is called pure if \(x_1\) and \(x_2\) have the same parity. Otherwise, the point is mixed. Find \(N(P)\) if \(P\) is a pure point or a mixed point.
(c)
In Activity 20.10 we show that the set \(S_1 = \{(1,-1), (1,1), (-1,1), (-1,-1)\}\) is not a digital path and so not a digital Jordan curve. Which part of Theorem 20.15 does \(S_1\) violate?
(d)
In Activity 20.10 we show that the set \(S_2 = \{(0,0), (1,-1), (2,0), (1,1)\}\) is a digital Jordan curve. Show that in \(S_2\text{,}\) the property from Theorem 20.15 that \(x_{j-1}\) and \(x_{j+1}\) and no other points are adjacent to \(x_j\) is satisfied for each \(j\text{.}\)
