@ Appl. Gen. Topol. 22, no. 1 (2021), 121-137doi:10.4995/agt.2021.14185
© AGT, UPV, 2021
Convexity and freezing sets in digital topology
Laurence Boxer
Department of Computer and Information Sciences, Niagara University, NY 14109, USA; and
Department of Computer Science and Engineering, State University of New York at Buffalo,
USA. (boxer@niagara.edu)
Communicated by V. Gregori
Abstract
We continue the study of freezing sets in digital topology, introduced
in [4]. We show how to find a minimal freezing set for a “thick” con-
vex disk X in the digital plane Z
2
. We give examples showing the
significance of the assumption that X is convex.
2010 MSC: 54H25.
Keywords: digital topology; freezing set; convexity; digital disk.
1. Introduction
We often use a digital image as a mathematical model of an object or a set
of objects “pictured” by the image. Methods inspired by classical topology
are used to determine whether a digital image has properties analogous to the
topological properties of a “real world” object represented by the image. The
literature now contains considerable success in adapting to digital topology
notions from classical topology such as connectedness, continuous function,
homotopy, fundamental group, homology, automorphism group, etc.
The fixed point properties (including “approximate fixed point” properties)
of a digital image are in some ways similar and in other ways very different
from those of the Euclidean object modeled by the image. This claim is borne
out in such papers as [8, 6, 7].
A large number of papers have been written to study fixed point properties
of digital images considered as digital metric spaces [12]. Most of assertions of
these papers have been shown [9, 2, 3, 5] to be incorrect or trivial; this leads
Received 12 August 2020 – Accepted 04 December 2020
http://dx.doi.org/10.4995/agt.2021.14185
L. Boxer
to the conclusion that the digital metric space is not an idea worth developing
further.
Knowledge of the fixed point set Fix(f) of a continuous self-map on a non-
trivial topological space X rarely tells us much about f|X\Fix(f). By contrast,
it was shown in [9, 4] that knowledge of the fixed point set Fix(f) of a digitally
continuous self-map on a nontrivial digital image (X, κ) may tell us a great
deal about f|X\Fix(f). Indeed, if A is a subset of X that is a “freezing set” and
A ⊂ Fix(f), then f is constrained to be the identity function idX.
Some results concerning freezing sets were presented in [4]. In this paper, we
continue the study of freezing sets. In particular, we show how to find minimal
freezing sets for “thick” convex disks in the digital plane, and we give examples
showing the importance of the assumption of convexity in our theorems.
2. Preliminaries
We use Z to indicate the set of integers and R for the set of real numbers.
For a finite set X, we denote by #X the number of distinct members of X.
2.1. Adjacencies. Material in this section is quoted or paraphrased from [4].
The cu-adjacencies are commonly used in digital topology. Let x, y ∈ Z
n,
x 6= y, where we consider these points as n-tuples of integers:
x = (x1, . . . , xn), y = (y1, . . . , yn).
Let u ∈ Z, 1 ≤ u ≤ n. We say x and y are cu-adjacent if
• there are at most u indices i for which |xi − yi| = 1, and
• for all indices j such that |xj − yj| 6= 1 we have xj = yj.
Often, a cu-adjacency is denoted by the number of points adjacent to a given
point in Zn using this adjacency. E.g.,
• In Z1, c1-adjacency is 2-adjacency.
• In Z2, c1-adjacency is 4-adjacency and c2-adjacency is 8-adjacency.
• In Z3, c1-adjacency is 6-adjacency, c2-adjacency is 18-adjacency, and
c3-adjacency is 26-adjacency.
For κ-adjacent x, y, we write x ↔κ y or x ↔ y when κ is understood. We
write x -κ y or x - y to mean that either x ↔κ y or x = y.
We say subsets A, B of a digital image X are (κ-)adjacent, A -κ B or A - B
when κ is understood, if there exist a ∈ A and b ∈ B such that a -κ b.
We say {xn}
k
n=0 ⊂ (X, κ) is a κ-path (or a path if κ is understood) from x0
to xk if xi -κ xi+1 for i ∈ {0, . . . , k − 1}, and k is the length of the path.
A subset Y of a digital image (X, κ) is κ-connected [15], or connected when
κ is understood, if for every pair of points a, b ∈ Y there exists a κ-path in Y
from a to b.
We define
N(X, κ, x) = {y ∈ X | x ↔κ y},
N∗(X, κ, x) = {y ∈ X | x -κ y} = N(X, κ, x) ∪ {x}.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 122
Convexity and freezing sets in digital topology
Definition 2.1. Let X ⊂ Zn.
• The boundary of X with respect to the ci adjacency, i ∈ {1, 2}, is
Bdi(X) = {x ∈ X | there exists y ∈ Z
n \ X such that y ↔ci x}.
Note Bd1(X) is what is called the boundary of X in [14]. However, for
this paper, Bd2(X) offers certain advantages.
• The interior of X with respect to the ci adjacency is Inti(X) = X \
Bdi(X).
2.2. Digitally continuous functions. Material in this section is quoted or
paraphrased from [4].
The following generalizes a definition of [15].
Definition 2.2 ([1]). Let (X, κ) and (Y, λ) be digital images. A function
f : X → Y is (κ, λ)-continuous if for every κ-connected A ⊂ X we have that
f(A) is a λ-connected subset of Y . If (X, κ) = (Y, λ), we say such a function
is κ-continuous, denoted f ∈ C(X, κ). ✷
When the adjacency relations are understood, we may simply say that f is
continuous. Continuity can be expressed in terms of adjacency of points:
Theorem 2.3 ([15, 1]). A function f : (X, κ) → (Y, λ) is continuous if and
only if x ↔κ x
′ in X implies f(x) -λ f(x
′).
Similar notions are referred to as immersions, gradually varied operators,
and gradually varied mappings in [10, 11].
Composition preserves continuity, in the sense of the following.
Theorem 2.4 ([1]). Let (X, κ), (Y, λ), and (Z, µ) be digital images. Let f :
X → Y be (κ, λ)-continuous and let g : Y → Z be (λ, µ)-continuous. Then
g ◦ f : X → Z is (κ, µ)-continuous.
Given X = Πvi=1Xi, we denote throughout this paper the projection onto
the ith factor by pi; i.e., pi : X → Xi is defined by pi(x1, . . . , xv) = xi, where
xj ∈ Xj.
Given a function f : X → X, we say x ∈ X is a fixed point of f if f(x) = x.
The set of points {x ∈ X | f(x) = x} we denote as Fix(f).
We use the notation idX to denote the identity function: idX : X → X is
the function idX(x) = x for all x ∈ X.
Definition 2.5 ([4]). Let (X, κ) be a digital image. We say A ⊂ X is a freezing
set for X if given f ∈ C(X, κ), A ⊂ Fix(f) implies f = idX.
2.3. Digital disks and bounding curves. Let κ ∈ {c1, c2}, n > 1. We say
a κ-connected set S = {xi}
n
i=1 ⊂ Z
2 is a (digital) line segment if the members
of S are collinear.
Remark 2.6. A digital line segment must be vertical, horizontal, or have slope
of ±1. We say a segment with slope of ±1 is slanted.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 123
L. Boxer
A (digital) κ-closed curve is a path S = {si}
m
i=0 such that s0 = sm, and
0 < |i − j| < m implies si 6= sj. If i, j < m and si ↔κ sj implies |i − j|
mod m = 1, S is a (digital) κ-simple closed curve. For a simple closed curve
S ⊂ Z2 we generally assume
• m ≥ 8 if κ = c1, and
• m ≥ 4 if κ = c2.
These requirements are necessary for the Jordan Curve Theorem of digital
topology, below, as a c1-simple closed curve in Z
2 needs at least 8 points to
have a nonempty finite complementary c2-component, and a c2-simple closed
curve in Z2 needs at least 4 points to have a nonempty finite complementary
c1-component. Examples in [14] show why it is desirable to consider S and
Z
2 \ S with different adjacencies.
Theorem 2.7 ([14], Jordan Curve Theorem for digital topology). Let {κ, κ′} =
{c1, c2}. Let S ⊂ Z
2 be a simple closed κ-curve such that S has at least 8 points
if κ = c1 and such that S has at least 4 points if κ = c2. Then Z
2 \S has exactly
2 κ′-connected components.
One of the κ′-components of Z2 \ S is finite and the other is infinite. This
suggests the following.
Definition 2.8. Let S ⊂ Z2 be a c2-closed curve such that Z
2 \ S has two
c1-components, one finite and the other infinite. The union D of S and the
finite c1-component of Z
2 \ S is a (digital) disk. S is a bounding curve of D.
The finite c1-component of Z
2 \ S is the interior of S, denoted Int(S), and the
infinite c1-component of Z
2 \ S is the exterior of S, denoted Ext(S).
Notes:
• If D is a digital disk determined as above by a bounding c2-closed curve
S, then (S, c1) can be disconnected. See Figure 1.
• There may be more than one closed curve S bounding a given disk D.
See Figure 2. Since we are interested in finding minimal freezing sets
and since it turns out we often compute these from bounding curves,
we may prefer those that are minimal bounding curves. A bounding
curve S for a disk D is minimal if there is no bounding curve S′ for D
such that #S′ < #S.
• In particular, a bounding curve need not be contained in Bd1(D). E.g.,
in the disk D shown in Figure 2(i), (2, 2) is a point of the bounding
curve; however, all of the points c1-adjacent to (2, 2) are members of D,
so by Definition 2.1, (2, 2) 6∈ Bd1(D). However, a bounding curve for
D must be contained in Bd2(D).
• In Definition 2.8, we use c2 adjacency for S and we do not require S
to be simple. Figure 2 shows why these seem appropriate.
– The use of c2 adjacency allows slanted segments in bounding curves
and makes possible a bounding curve in subfigure (ii) with fewer
points than the bounding curve in subfigure (i) in which adjacent
pairs of the bounding curve are restricted to c1 adjacency.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 124
Convexity and freezing sets in digital topology
Figure 1. The c1-disk D = {(x, y) ∈ Z
2 | |x| + |y| < 2}. The
bounding curve S = {(x, y) ∈ Z2 | |x| + |y| = 1} = D \ {(0, 0)}
is not c1-connected.
Figure 2. Two views of [0, 3]2
Z
\ {(3, 3)}, which can be re-
garded as a c1-disk with either of the closed curves shown in
dark as a bounding curve.
(i) The dark line segments show a c1-simple closed curve S
that is a bounding curve for D.
(ii) The dark line segments show a c2-closed curve S that is a
minimal bounding curve for D.
Note the point (2, 2) in the bounding curve shown in (i). By
Definition 2.1, (2, 2) 6∈ Bd1(D); however, (2, 2) ∈ Bd2(D).
– Neither of the bounding curves shown in Figure 2 is a c2-simple
closed curve. E.g., non-consecutive points of each of the bound-
ing curves, (0, 1) and (1, 0), are c2-adjacent. The bounding curve
shown in Figure 2(ii) is clearly also not a c1-simple closed curve.
• A closed curve that is not simple may be the boundary Bd2 of a digital
image that is not a disk. This is illustrated in Figure 3.
More generally, we have the following.
Definition 2.9. let X ⊂ Z2 be a finite, ci-connected set, i ∈ {1, 2}. Suppose
there are pairwise disjoint c2-closed curves Sj ⊂ X, 1 ≤ j ≤ n, such that
• X ⊂ S1 ∪ Int(S1);
• for j > 1, Dj = Sj ∪ Int(Sj) is a digital disk;
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 125
L. Boxer
Figure 3. D = [0, 6]Z×[0, 2]Z\{(3, 2)} shown with a bounding
curve S in dark segments. D is not a disk with either the c1 or
the c2 adjacency, since with either of these adjacencies, Z
2 \ S
has two bounded components, {(1, 1), (2, 1)} and
{(4, 1), (5, 1)}.
• no two of
S1 ∪ Ext(S1), D2, . . . , Dn
are c1-adjacent or c2-adjacent; and
• we have
Z
2 \ X = Ext(S1) ∪
n⋃
j=2
Int(Sj).
Then {Sj}
n
j=1 is a set of bounding curves of X.
Note: As above, a digital image X ⊂ Z2 may have more than one set of
bounding curves.
A set X in a Euclidean space Rn is convex if for every pair of distinct points
x, y ∈ X, the line segment xy from x to y is contained in X. The convex hull of
Y ⊂ Rn, denoted hull(Y ), is the smallest convex subset of Rn that contains Y .
If Y ⊂ R2 is a finite set, then hull(Y ) is a single point if Y is a singleton; a line
segment if Y has at least 2 members and all are collinear; otherwise, hull(Y )
is a polygonal disk, and the endpoints of the edges of hull(Y ) are its vertices.
A digital version of convexity can be stated for subsets of the digital plane Z2
as follows. A finite set Y ⊂ Z2 is (digitally) convex if either
• Y is a single point, or
• Y is a digital line segment, or
• Y is a digital disk with a bounding curve S such that the endpoints of
the maximal line segments of S are the vertices of hull(Y ) ⊂ R2.
Let s1 and s2 be sides of a digital disk X ⊂ Z
2, i.e., maximal digital line
segments in a bounding curve S of X, such that s1 ∩ s2 = {p} ⊂ X. The
interior angle of X at p is the angle formed by s1, s2, and Int(X).
Remark 2.10. Let (X, κ) be a digital disk in Z2, κ ∈ {c1, c2}. Let s1 and s2 be
sides of X such that s1 ∩ s2 = {p} ⊂ X. Then the interior angle of X at p is
well defined.
Proof. If there exists q ∈ X \ (s1 ∪ s2) such that q ↔c2 p, then the interior
angle of X at p is the angle obtained by rotating s1 about p through q to reach
s2.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 126
Convexity and freezing sets in digital topology
Figure 4. Illustration of Lemma 2.13. Arrows show the im-
ages of q, q′ under f ∈ C(X, c2). Since f(q) is to the right of q
and q′ ↔c1,c2 q with q
′ to the left of q, f pulls q′ to the right
so that f(q′) is to the right of q′.
Otherwise, the angles formed by s1 and s2 measure 45
◦ (π/4 radians) and
315◦ (7π/4 radians). Since X is convex, the 45◦ angle determined by s1 and s2
is the interior angle of X at p. �
Remark 2.11. It follows from Remark 2.6 that every interior angle measures as
a multiple of 45◦ (π/4 radians). For a convex disk, an interior angle must be
45◦ (π/4 radians), 90◦ (π/2 radians), or 135◦ (3π/4 radians).
2.4. Tools for determining fixed point sets. The following assertions will
be useful in determining fixed point and freezing sets.
Proposition 2.12 (Corollary 8.4 of [9]). Let (X, κ) be a digital image and
f ∈ C(X, κ). Suppose x, x′ ∈ Fix(f) are such that there is a unique shortest
κ-path P in X from x to x′. Then P ⊂ Fix(f).
Lemma 2.13 below is in the spirit of “pulling” as introduced in [13]. We
quote [4]:
The following assertion can be interpreted to say that in a
cu-adjacency, a continuous function that moves a point p also
[pulls along] a point that is “behind” p. E.g., in Z2, if q and
q′ are c1- or c2-adjacent with q left, right, above, or below q
′,
and a continuous function f moves q to the left, right, higher,
or lower, respectively, then f also moves q′ to the left, right,
higher, or lower, respectively.
Lemma 2.13 ([4]). Let (X, cu) ⊂ Z
n be a digital image, 1 ≤ u ≤ n. Let
q, q′ ∈ X be such that q ↔cu q
′. Let f ∈ C(X, cu).
(1) If pi(f(q)) > pi(q) > pi(q
′) then pi(f(q
′)) > pi(q
′).
(2) If pi(f(q)) < pi(q) < pi(q
′) then pi(f(q
′)) < pi(q
′).
Figure 4 illustrates Lemma 2.13.
Theorem 2.14 ([4]). Let X ⊂ Zn be finite. Then for 1 ≤ u ≤ n, Bd1(X) is a
freezing set for (X, cu).
Remark 2.15. A similar proof can be used to show that if X ⊂ Z2 is finite,
then a set of bounding curves for X is a freezing set for (X, ci), i ∈ {1, 2}.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 127
L. Boxer
Theorem 2.16. Let D be a digital disk in Z2. Let S be a bounding curve for
D. Then S is a freezing set for (D, c1) and for (D, c2).
Proof. This is like the proof of Theorem 2.14 in [4]. Let κ ∈ {c1, c2}. Let
f ∈ C(D, κ) such that S ∈ Fix(f). Suppose there exists x ∈ D such that
f(x) 6= x. Then x lies on a horizontal segment ab and on a vertical segment cd
such that {a, b, c, d} ⊂ S, p1(a) < p1(b), and p2(c) < p2(d).
• If p1(f(x)) > p1(x) then by Lemma 2.13, p1(f(a)) > p1(a), contrary
to a ∈ S ⊂ Fix(f).
• If p1(f(x)) < p1(x) then by Lemma 2.13, p1(f(b)) < p1(b), contrary to
b ∈ S ⊂ Fix(f).
• If p2(f(x)) > p2(x) then by Lemma 2.13, p1(f(c)) > p1(c), contrary to
c ∈ S ⊂ Fix(f).
• If p2(f(x)) < p2(x) then by Lemma 2.13, p1(f(d)) < p1(d), contrary to
d ∈ S ⊂ Fix(f).
In all cases, we have a contradiction brought on by assuming x 6∈ Fix(f).
Therefore, f = idD, so S is a freezing set for (D, κ). �
We will use the following.
Definition 2.17. Let (X, κ) be a digital image. Let p, q ∈ X such that
N(X, p, κ) ⊂ N∗(X, q, κ).
Then q is a close κ-neighbor of p.
Lemma 2.18. Let (X, κ) be a digital image. Let p, q ∈ X such that q is a close
κ-neighbor of p. Then there is a κ-retraction r : X → X of X to X \ {p}.
Proof. This was shown in the proof of Lemma 4.8 of [9]. �
Lemma 2.19. Let (X, κ) be a digital image. Let p, q ∈ X such that q is a
close κ-neighbor of p. Then p belongs to every freezing set of (X, κ).
Proof. Let A be a freezing set of (X, κ). It follows from Lemma 2.18 that
A \ {p} is not a freezing set of (X, κ). The assertion follows. �
3. c1-Freezing sets for disks in Z
2
The following can be interpreted as stating that the set of “corner points”
form a freezing set for a digital cube with the c1 adjacency.
Theorem 3.1 ([4]). Let X = Πni=1[0, mi]Z. Let A = Π
n
i=1{0, mi}. Then A is
a freezing set for (X, c1); minimal for n ∈ {1, 2}.
Remark 3.2. Example 5.16 of [4] shows that the freezing set of Theorem 3.1 is
not minimal for n = 3.
The argument used to prove Theorem 3.1 may lead one to ask if this theorem
can be generalized for n = 2 as follows:
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 128
Convexity and freezing sets in digital topology
Given a digital disk D ⊂ Z2 such that all of the maximal
segments of a bounding curve S of D are horizontal or vertical,
is the set of the endpoints of the maximal segments of S a
minimal freezing set for (D, c1)?
The following provides a negative answer to this question.
Example 3.3. Let D = [0, 3]Z × [0, 6]Z \ {(3, 3)}). Then
A = {(0, 0), (3, 0), (3, 2), (3, 4), (3, 6), (0, 6)}
(see Figure 5(i)) is a minimal freezing set for (D, c1). Note (2, 2) and (2, 4) are
endpoints of maximal horizontal and vertical bounding segments of D and are
not members of A. While (2, 2) and (2, 4) are members of a bounding curve
for D, they are not members of a minimal bounding curve, which includes edges
from (3, 4) to (2, 3) and from (2, 3) to (3, 2) (see Figure 5(ii)).
Proof. Let f ∈ C(D, c1) such that A ⊂ Fix(f). It follows from Proposition 2.12
that the vertical segments {0} × [0, 6]Z, {3} × [0, 2]Z, and {3} × [4, 6]Z, the
horizontal segments [0, 3]Z × {0} and [0, 3]Z × {6}, and the path
{(3, 2), (2, 2), (2, 3), (2, 4), (3, 4)}
are all subsets of Fix(f). Since the union of these paths is a bounding curve S
for D, we have S ⊂ Fix(f). That A is a freezing set follows from Theorem 2.16.
To show A is a minimal freezing set, we observe that the following are pairs
(p, q) such that p ∈ A and q is a close c1-neighbor of p (see Figure 5):
((0, 0), (1, 1)), ((3, 0), (2, 1)), ((3, 2), (2, 1)), ((3, 4), (2, 5)),
((3, 6), (2, 5)), and ((0, 6), (1, 5)).
By Lemma 2.19, every member of A must belong to every freezing set of (X, c1).
It follows that A is a minimal freezing set. �
Definition 3.4. Let X ⊂ Z2 be a digital disk. We say X is thick if the following
are satisfied. For some bounding curve S of X,
• for every slanted segment S of Bd2(X), if p ∈ S is not an endpoint of
S, then there exists c ∈ X such that (see Figure 6)
(3.1) c ↔c2 p 6↔c1 c,
and
• if p is the vertex of a 90◦ (π/2 radians) interior angle θ of S, then there
exists q ∈ Int(X) such that
– if θ has horizontal and vertical sides then q ↔c2 p 6↔c1 q (see
Figure 7);
– if θ has slanted sides then q ↔c1 p (see Figure 8);
and
• if p is the vertex of a 135◦ (3π/4 radians) interior angle θ of S, there
exist b, b′ ∈ X such that b and b′ are in the interior of θ and (see
Figure 9)
b ↔c2 p 6↔c1 b and b
′ ↔c1 p.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 129
L. Boxer
Figure 5. There are distinct boundary curves for the disk D
that contain the horizontal segments from (0, 0) to (3, 0) and
from (0, 6) to (3, 6); and vertical segments from (0, 0) to (0, 6),
from (3, 0) to (3, 2), and from (3, 4) to (3, 6).
(i) We can complete a boundary curve by using the horizontal
segments from (2, 2) to (3, 2) and from (2, 4) to (3, 4) and the
vertical segment from (2, 2) to (2, 4), as shown in dark. This
lets us view D as a disk with horizontal and vertical sides.
Members of the minimal freezing set A for (D, c1), determined
in Example 3.3, are marked “a”. Note {(2, 2), (2, 4)} ∩ A =
∅. (2, 2) and (2, 4) are endpoints of a maximal horizontal
segment of a bounding curve, but not of the minimal bounding
curve S; the latter is shown in (ii). Indeed, by Definition 2.8,
{(2, 2), (2, 4)} ⊂ Int(D).
(ii) Alternately, we can complete a boundary curve by using
the slanted line segments from (2, 3) to (3, 4) and from (2, 3)
to (3, 2). This is a minimal boundary curve S that lets us view
D as in Example 4.1. A minimal freezing set for (D, c2) is
S \ {(2, 3)}.
Examples of digital images that fail to be thick are shown in Figure 10.
The following expands on the dimension 2 case of Theorem 3.1 to give a
subset of Bd(X) that is a freezing set.
Theorem 3.5. Let X be a finite digital image in Z2 with a set of bound-
ing curves Si, 1 ≤ i ≤ n, as in Definition 2.9. Let A1 be the set of points
x ∈
⋃n
i=1 Si such that x is an endpoint of a maximal horizontal or a maxi-
mal vertical edge of
⋃n
i=1 Si. Let A2 be the union of slanted line segments in⋃n
i=1 Si. Then A = A1 ∪ A2 is a freezing set for (X, c1).
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 130
Convexity and freezing sets in digital topology
Figure 6. p ∈ uv in a bounding curve, with uv slanted. Note
u 6↔c1 p 6↔c1 v, p ↔c2 c 6↔c1 p, {p, c} ⊂ N(Z
2, c1, b) ∩
N(Z2, c1, d). If X is thick then c ∈ X. (Not meant to be
understood as showing all of X.)
Figure 7. ∠apb is a 90◦ (π/2 radians) angle of a bounding
curve of X at p ∈ A1, with horizontal and vertical sides. If
X is thick then q ∈ Int(X). (Not meant to be understood as
showing all of X.)
Figure 8. ∠apb is a 90◦ (π/2 radians) angle between slanted
segments of a bounding curve. If X is thick then q ∈ Int(X).
(Not meant to be understood as showing all of X).
Figure 9. ∠apq is an angle of 135◦ degrees (3π/4 radians)
of a bounding curve of X at p, with ap ∪ pq a subset of the
bounding curve. If X is thick then b, b′ ∈ X. (Not meant to
be understood as showing all of X.)
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 131
L. Boxer
Figure 10. Digital disks that are not thick.
(i) (1, 2) is a non-endpoint of a slanted boundary segment for
which there is no point corresponding to c of Figure 6.
(ii) (0, 1) is the vertex of a 90◦-degree (π/2 radians) interior
angle but is not c2-adjacent to any member of the interior
of the disk. Note the segment from (1,1) to (2,0) belongs
to a minimal bounding curve, so (2,1) is an interior point.
Therefore, this image really is a disk.
(iii) (0, 2) is the vertex of a 135◦ interior angle of a bounding
curve for which there is no point corresponding to b of Figure 9.
Proof. Let f ∈ C(X, c1) such that A ⊂ Fix(f). Let x, x
′ be distinct members
of A1 that are endpoints of the same maximal horizontal or vertical edge E
in some Si. Then E is the unique shortest c1-path in X from x to x
′. By
Proposition 2.12, E ⊂ Fix(f). It follows that every horizontal and every vertical
side of Si belongs to Fix(f). By hypothesis we also have that A2 ⊂ Fix(f), so
Si ⊂ Fix(f). Therefore, Bd2(X) ⊂ Fix(f). By Remark 2.15, f = idX. Thus A
is a freezing set for (X, c1). �
Remark 3.6. The set A of Theorem 3.5 need not be minimal. This is shown in
Example 3.3, where (2, 3), as a member of a slanted edge of a minimal bounding
curve (see Figure 5), is a member of the set A of Theorem 3.5, but is not a
member of the minimal freezing set.
Theorem 3.7. Let X be a thick convex disk with a bounding curve S. Let A1
be the set of points x ∈ S such that x is an endpoint of a maximal horizontal or
a maximal vertical edge of S. Let A2 be the union of slanted line segments in
S. Then A = A1 ∪ A2 is a minimal freezing set for (X, c1) (see Figure 11(ii)).
Proof. That A is a freezing set follows as in the proof of Theorem 3.5. To show
A is minimal, we must show that if we remove a point p from A, the remaining
set A \ {p} is not a freezing set.
We start by considering p ∈ A1. Since X is convex, the interior angle of S
at p must be 45◦ (π/4 radians), 90◦ (π/2 radians), or 135◦ (3π/4 radians).
• Suppose the interior angle of S at p is 45◦ (π/4 radians). Let b be a
point of S that is c1-adjacent to p on the horizontal or vertical edge of
this angle (see Figure 12). Then b is a close c1-neighbor of p in X. By
Lemma 2.19, X \ {p} is not a freezing set for (X, c2).
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 132
Convexity and freezing sets in digital topology
Figure 11. The convex disk D = [0, 4]2
Z
\{(0, 3), (0, 4), (1, 4)}.
The dashed segment from (0, 2) to (2, 4) shown in (i) and (ii)
indicates part of the bounding curve and not c1-adjacencies.
(i) D with a c2 bounding curve.
(ii) (D, c1) with members of a minimal freezing set A marked
“a” - these are the endpoints of the maximal horizontal and
vertical segments of the bounding curve, and all points of the
slanted segment of the bounding curve, per Theorem 3.5.
(iii) (D, c2) with members of a minimal freezing set B marked
“b” - these are the endpoints of the maximal slanted edge
and all the points of the horizontal and vertical edges of the
bounding curve, per Theorem 4.2.
Figure 12. ∠apb is a 45◦ (π/4 radians) interior angle of a
bounding curve at p ∈ A1. (Not meant to be understood as
showing all of X.)
• Suppose the interior angle of S at p is 90◦ (π/2 radians). Let a, b be
the points of S that are c1-adjacent to p on the horizontal and vertical
edges of this angle and let q be the point of Int(X) that is c1-adjacent
to each of a and b (see Figure 7).
Then q is a close c1-neighbor of p in X. Thus, A \ {p} is not a
freezing set for (X, c1).
• Suppose the interior angle of S at p is 135◦ (3π/4 radians). Let a, q ∈ S
be such that a and q are the members of this angle that are c2-adjacent
to p, where ap is slanted and pq is horizontal or vertical. Since X is
thick, Definition 3.4 yields that there exists b ∈ X such that b ↔c2 p (as
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 133
L. Boxer
in Figure 9). Then b is a close c1-neighbor of p in X. By Lemma 2.19,
A \ {p} is not a freezing set for (X, c1).
Thus we have shown that if p ∈ A1 then A\{p} is not a freezing set for (X, c1).
Now we wish to show if p ∈ A2 then A \ {p} is not a freezing set for (X, c1).
Let s be a slanted segment of Bd2(X) containing p.
If p is not an endpoint of s, then from the assumption (3.1) there exist
b, c, d ∈ X such that p ↔c2 c, p 6↔c1 c, and b ↔c1 c ↔c1 d (see Figure 6). Then
c is a close c1-neighbor of p in X. By Lemma 2.19, A \ {p} is not a freezing set
for (X, c1).
If p is an endpoint of s, let s′ be the other maximal segment of Bd2(X) for
which p is an endpoint. If s′ is horizontal or vertical, then p ∈ A1, hence, as
discussed above, A \ {p} is not a freezing set for (X, c1). Therefore, we assume
s′ is slanted. Since X is convex and both s and s′ are slanted, the interior angle
of S at p must be 90◦ (π/2 radians). There exists q ∈ Int(X) such that q ↔c1 p
(see Figure 8). Then q is a close c1-neighbor of p in X. By Lemma 2.19, A\{p}
is not a freezing set for (X, c1). �
4. c2-Freezing sets for disks in Z
2
For disks in Z2, we obtain results for the c2 adjacency that are dual to those
obtained for the c1 adjacency in the previous section.
As was true of the c1 adjacency and Theorem 3.5, we see, by comparing
Example 4.1 and Theorem 4.3 below, that with c2 adjacency, convexity can
affect determination of a minimal freezing set for a digital image in Z2.
Example 4.1. Let D = [0, 3]Z × [0, 6]Z \ {(3, 3)}). (This is the set used in
Example 3.3. See Figure 5.) Let S be the bounding curve shown in Figure 5(ii),
i.e., S is the union of the vertical segments {0} × [0, 6]Z, {3} × [0, 2]Z, and
{3} × [4, 6]Z; the horizontal segments [0, 3]Z × {0} and [0, 3]Z × {6}; and the
slanted segments (2, 3)(3, 4) and (2, 3)(3, 2).
Let B = S \ {(2, 3)}. Then B is a minimal freezing set for (D, c2).
Proof. Let f ∈ C(D, c2) be such that
(4.1) f|B = idB .
Let p = (2, 3), q = (3, 2) ∈ B, s = (3, 4) ∈ B. Note the following:
• If p1(f(p)) > p1(p) then by Lemma 2.13, p1(f(1, 3)) > 1 and therefore
p1(f(0, 3)) > 0, contrary to (4.1).
• If p1(f(p)) < p1(p) then by Lemma 2.13, p1(f(q)) < 3, contrary
to (4.1).
• If p2(f(p)) > p2(p) then by Lemma 2.13, p2(f(q)) > 2, contrary
to (4.1).
• If p2(f(p)) < p2(p) then by Lemma 2.13, p1(f(s)) < 4, contrary
to (4.1).
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 134
Convexity and freezing sets in digital topology
It follows that p ∈ Fix(f). Thus B∪{p} = Bd1(D) ⊂ Fix(f). By Theorem 2.14,
f = idD. This establishes that B is a freezing set.
To show B is minimal, for b ∈ B notice that there is a c2-close neighbor
q ∈ X:
(1, 1) is a c2-close neighbor of (0, 0) ∈ B;
(i, 1) is a c2-close neighbor of (i, 0) ∈ B, i ∈ {1, 2};
(1, j) is a c2-close neighbor of (0, j) ∈ B, 1 < j < 5;
(1, 5) is a c2-close neighbor of (0, 6) ∈ B;
(i, 5) is a c2-close neighbor of (i, 6) ∈ B, i ∈ {1, 2};
(2, 5) is a c2-close neighbor of (3, 6) ∈ B;
(2, j) is a c2-close neighbor of (3, j) ∈ B, j ∈ {1, 2, 4, 5}.
By Lemma 2.19, B \ {b} is not a freezing set for (D, c2). The assertion follows.
�
Theorem 4.2. Let X be a finite digital image in Z2 with a set of bounding
curves Si, 1 ≤ i ≤ n, as in Definition 2.9. Let B1 be the set of points x ∈⋃n
i=1 Si such that x is an endpoint of a maximal slanted edge in
⋃n
i=1 Si. Let
B2 be the union of maximal horizontal and maximal vertical line segments in⋃n
i=1 Si. Let B = B1 ∪ B2. Then B is a freezing set for (X, c2).
Proof. Let f ∈ C(X, c2) such that f|B = idB.
Let p be a point of a slanted edge E of
⋃n
i=1 Si such that p 6∈ B1. Let s
and s′ be the endpoints of E. If f(p) 6= p, it follows from Lemma 2.13 that
either f(s) 6= s or f(s′) 6= s′, a contradiction since by hypothesis we have
{s, s′} ⊂ Fix(f). Therefore, p ∈ Fix(f); hence, every slanted edge of
⋃n
i=1 Si
is a subset of Fix(f). Since by hypothesis all horizontal and vertical edges of⋃n
i=1 Si belong to Fix(f), we conclude that
⋃n
i=1 Si ⊂ Fix(f). It follows from
Remark 2.15 that f = idX. Thus, B is a freezing set for (X, c2). �
Theorem 4.3. Let X be a thick convex disk with a bounding curve S. Let B1
be the set of points x ∈ S such that x is an endpoint of a maximal slanted edge
in S. Let B2 be the union of maximal horizontal and maximal vertical line
segments in S. Let B = B1 ∪ B2. Then B is a minimal freezing set for (X, c2)
(see Figure 11(iii)).
Proof. That B is a freezing set follows as in the proof of Theorem 4.2. To show
B is a minimal freezing set, we must show that B \ {p} is not a freezing set for
every p ∈ B.
We start with p ∈ B1. Since X is a convex disk, we only have the following
possibilities to consider.
• X has an interior angle θ at p of 45◦ (π/4 radians). Let a ∈ X be such
that a ↔c2 p and a is adjacent to p on, say, the slanted edge of θ (see
Figure 12). Then a is a c2-close neighbor of p in X. By Lemma 2.19,
B \ {p} is not a freezing set for (X, c2).
• X has an interior angle at p of 90◦ (π/2 radians). Then there is a point
q ∈ Int(X) such that p ↔c1 q as in Figure 8. Then q is a c2-close
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 135
L. Boxer
Figure 13. p ∈ ab, a segment of the bounding curve S. q ∈
Int(X). p ↔c1 q. (Not meant to be understood as showing all
of X.)
neighbor of p in X. By Lemma 2.19, B \ {p} is not a freezing set for
(X, c2).
• X has an interior angle at p of 135◦ (3π/4 radians). Since X is thick,
there is a point b′ as in Figure 9 that is a close c2-neighbor of p. By
Lemma 2.19, B \ {p} is not a freezing set for (X, c2).
Now consider p as a member of B2. Since X is convex, this leaves only the
following possibilities.
• X has an interior angle at p of 45◦ (π/4 radians). Then p ∈ B1 ∩ B2 ⊂
B1. As discussed above, B \ {p} is not a freezing set for (X, c2).
• X has an interior angle at p of 90◦ (π/2 radians). Let a and b be
the points of the horizontal and vertical segments of Bd(X) such that
a ↔c1 p ↔c1 b and let q ∈ Int(X) be the point such that a ↔c1 q ↔c1 b
(see Figure 7). Then q is a close c2-neighbor of p in X. By Lemma 2.19,
B \ {p} is not a freezing set for (X, c2).
• X has an interior angle at p of 135◦ (3π/4 radians). Then p ∈ B1∩B2 ⊂
B1. As shown above, B \ {p} is not a freezing set for (X, c2).
• p is not an endpoint of its segment of Bd(X). Then p has a c1-close
neighbor q ∈ X (see Figure 13). By Lemma 2.19, B \ {p} is not a
freezing set for (X, c2).
We have shown that for all p ∈ B, B \ {p} is not a freezing set for (X, c2).
Therefore, B is a minimal freezing set for (X, c2). �
5. Further remarks
Let X be a thick convex digital disk in Z2 . We have shown how to find
minimal freezing sets for (X, c1) and for (X, c2). We have given examples
showing that our assertions do not extend to non-convex disks in Z2. However,
for non-convex disks in Z2 we have shown how to obtain smaller freezing sets
than were previously known. We have also obtained results for freezing sets of
c1- and c2-connected finite subsets of Z
2 bounded by multiple bounding curves.
We have left unanswered the following.
Question 5.1. Is every convex disk in Z2 thick?
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 136
Convexity and freezing sets in digital topology
Acknowledgements. The suggestions and corrections of the anonymous re-
viewers are gratefully acknowledged.
References
[1] L. Boxer, A classical construction for the digital fundamental group, Journal of Mathe-
matical Imaging and Vision 10 (1999), 51–62.
[2] L. Boxer, Remarks on fixed point assertions in digital topology, 2, Applied General
Topology 20, no. 1 (2019), 155–175.
[3] L. Boxer, Remarks on fixed point assertions in digital topology, 3, Applied General
Topology 20, no. 2 (2019), 349–361.
[4] L. Boxer, Fixed point sets in digital topology, 2, Applied General Topology 21, no. 1
(2020), 111–133.
[5] L. Boxer, Remarks on fixed point assertions in digital topology, 4, Applied General
Topology 21, no. 2 (2020), 265–284.
[6] L. Boxer, Approximate fixed point properties in digital topology, Bulletin of the Inter-
national Mathematical Virtual Institute 10, no. 2 (2020), 357–367.
[7] L. Boxer, Approximate fixed point property for digital trees and products, Bulletin of
the International Mathematical Virtual Institute 10, no. 3 (2020), 595–602.
[8] L. Boxer, O. Ege, I. Karaca, J. Lopez and J. Louwsma, Digital fixed points, approximate
fixed points, and universal functions, Applied General Topology 17, no. 2 (2016), 159–
172.
[9] L. Boxer and P. C. Staecker, Fixed point sets in digital topology, 1, Applied General
Topology 21, no. 1 (2020), 87–110.
[10] L. Chen, Gradually varied surfaces and its optimal uniform approximation, SPIE Pro-
ceedings 2182 (1994), 300–307.
[11] L. Chen, Discrete Surfaces and Manifolds, Scientific Practical Computing, Rockville,
MD, 2004.
[12] O. Ege and I. Karaca, Banach fixed point theorem for digital images, Journal of Non-
linear Sciences and Applications 8 (2015), 237û-245.
[13] J. Haarmann, M. Murphy, C. S. Peters and P. C. Staecker, Homotopy equivalence in
finite digital images, Journal of Mathematical Imaging and Vision 53 (2015), 288–302.
[14] A. Rosenfeld, Digital topology, The American Mathematical Monthly 86, no. 8 (1979),
621–630.
[15] A. Rosenfeld, ‘Continuous’ functions on digital pictures, Pattern Recognition Letters 4
(1986), 177–184.
© AGT, UPV, 2021 Appl. Gen. Topol. 22, no. 1 137