Skip to main content

Topology: An Inquiry-Based Approach

Steven Schlicker

πŸ”—

Section Applications 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 R3, but a computer screen represents information in Z2 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.
πŸ”—
Figure 20.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 Z2, the 4-neighbors of (x,y) are the points vertically or horizontally adjacent to (x,y): that is, the points (xΒ±1,y) and (x,yΒ±1). The 8-neighbors of (x,y) are the 4-neighbors along with the points diagonally adjacent to (x,y): that is, (xΒ±1,y), (x,yΒ±1), (xΒ±1,yΒ±1). 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, a k-path is a finite sequence p0, p1, …, pm in Z2 such that p1 is a k-neighbor of p2, p2 is a k-neighbor of p3, …, and pmβˆ’1 is a k-neighbor of pm.
πŸ”—

Activity 20.9.

πŸ”—

(a)

πŸ”—
Show that there is a 4-path connecting any two points in Z2. Then explain why there is an 8-path connecting any two points in Z2.
πŸ”—

(b)

πŸ”—
In the continuous case, every Jordan curve separates R2 into two connected regions. To have a similar theorem in the discrete case, we need a notion of connectedness in Z2. 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 Z2. Since connectedness and path connectedness are equivalent in finite topological spaces, we us the idea of k-paths to define connectedness in Z2. We say that a subset S of Z2 is kβˆ’connected if if any two of its points can be joined by a k-path in S. 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 S1 be the set illustrated at left in Figure 20.11 and S2 the set at right.
Figure 20.11. Sets S1 (left) and S2 (right) in the digital plane.
πŸ”—
Is S1 4 connected? Is S1 8 connected? Verify your answer. Repeat with S2.
πŸ”—

(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 S1 a Jordan 4-curve? Is S1 a Jordan 8-curve? Verify your answer. Repeat with S2.
πŸ”—

(d)

πŸ”—
As usual, we define a component to be a maximal connected set. Explain why S1 is a Jordan 8-curve whose complement is connected and why S2 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. 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 Z2 into exactly two 8-components, and a Jordan 8-curve with at least five points separates Z2 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.
πŸ”—

Activity 20.10.

πŸ”—
πŸ”—
Consider Z with the topology Ο„1 with basis {B(n)}, where
B(n)={{n} if n is odd ,{nβˆ’1,n,n+1} if n is even .
πŸ”—
This topology is called the digital line topology or the Khalimsky topology on Z. 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 Z2 we use the product topology. Explain why the collection of sets {B(m,n)} where
B(m,n)={{(m,n)}m and n odd, {(mβˆ’i,nβˆ’j)βˆ£βˆ’1≀i≀1,βˆ’1≀j≀1}m and n even, {(m,nβˆ’1),(m,n),(m,n+1)}m odd and n even, {(mβˆ’1,n),(m,n),(m+1,n)}m even and n odd 
πŸ”—
is a basis for the Khalimsky topology Ο„2 on Z2. (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 z1<z2 in (Z,Ο„1), the digital interval [z1,z2] is the set
[z1,z2]={z∈Z∣z1≀z≀z2}.
πŸ”—
The integers z1 and z2 are called the endpoints of the digital interval [z1,z2].
πŸ”—
Definition 20.12.
πŸ”—
πŸ”—
Let X be a topological space.
  • πŸ”—
    A digital path in X is the range of a continuous function from a digital interval to X.
  • πŸ”—
    A digital arc in X is the range of a homeomorphism from a digital interval to X.
πŸ”—
πŸ”—
Let
S1={(1,βˆ’1),(1,1),(βˆ’1,1),(βˆ’1,βˆ’1)},S2={(0,0),(1,βˆ’1),(2,0),(1,1)}, and S3={(1,βˆ’1),(1,0),(1,1),(0,1),(βˆ’1,1),(βˆ’1,0),(βˆ’1,βˆ’1),(0,βˆ’1)}.
πŸ”—
Show that S1 is not a digital path but S2 and S3 are digital paths.
πŸ”—

(d)

πŸ”—
To produce a digital Jordan Curve Theorem, we need a definition of a digital Jordan curve.
πŸ”—
Definition 20.13.
πŸ”—
A digital Jordan curve is a finite connected set J with |J|β‰₯4 such that Jβˆ–{j} is a digital arc for each j∈J.
πŸ”—
So every digital Jordan curve is a connected set. Show that any finite digital path in Z2 is a connected set.
Hint.
Is every digital interval connected?
πŸ”—

(e)

πŸ”—
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).
πŸ”—
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 S2 is a digital Jordan curve (and thus splits Z2 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.
πŸ”—
We investigate this theorem in the next activity.
πŸ”—

Activity 20.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β‰ y and the set {x,y} is connected. Then let N(x) to be the intersection of all neighborhoods of x. Show that distinct elements x and y in a topological space X are adjacent if and only if x∈N(y) or y∈N(x).
πŸ”—

(b)

πŸ”—
A point (x1,x2) in Z2 is called pure if x1 and x2 have the same parity. Otherwise, the point is mixed. Find N(P) if P is a pure point or a mixed point.
πŸ”—

(d)

πŸ”—
In Activity 20.10 we show that the set S2={(0,0),(1,βˆ’1),(2,0),(1,1)} is a digital Jordan curve. Show that in S2, the property from Theorem 20.15 that xjβˆ’1 and xj+1 and no other points are adjacent to xj is satisfied for each j.
<Prev^TopNext>