Sébastien Fourey
email: fourey@greyc.ismra.fr

T Yung Kong
email: ykong@cs.qc.edu

Gabor T Herman
email: gherman@gc.cuny.edu

Generic Axiomatized Digital Surface-Structures

Abstract

In digital topology, Euclidean n-space R n is usually modeled either by the set of points of a discrete grid, or by the set of n-cells in a convex cell complex whose union is R n . For commonly used grids and complexes in the cases n = 2 and 3, certain pairs of adjacency relations (κ, λ) on the grid points or n-cells (such as [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF] and [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Herman | Oriented surfaces in digital spaces[END_REF] on Z 2 ) are known to be "good pairs." For these pairs of relations (κ, λ), many results of digital topology concerning a set of grid points or n-cells and its complement (such as Rosenfeld's digital Jordan curve theorem) have versions in which κ-adjacency is used to define connectedness on the set and λ-adjacency is used to define connectedness on its complement. At present, results of 2D and 3D digital topology are often proved for one good pair of adjacency relations at a time; for each result there are different (but analogous) theorems for different good pairs of adjacency relations. In this paper we take the first steps in developing an alternative approach to digital topology based on very general axiomatic definitions of "well-behaved digital spaces." This approach gives the possibility of stating and proving results of digital topology as single theorems which apply to all spaces of the appropriate dimensionality that satisfy our axioms. Specifically, this paper introduces the notion of a generic axiomatized digital surface-structure (gads)a general, axiomatically defined, type of discrete structure that models subsets of the Euclidean plane and of other surfaces. Instances of this notion include gads corresponding to all of the good pairs of adjacency relations that have previously been used (by ourselves or others) in digital topology on planar grids or on boundary surfaces. We define basic concepts for a gads (such as homotopy of paths and the intersection number of two paths), give a discrete definition of planar gads (which are gads that model subsets of the Euclidean plane) and present some fundamental results including a Jordan curve theorem for planar gads.

Introduction

In digital topology, Euclidean n-space R n is usually modeled either by the set of points of a discrete grid, or by the set of n-cells in a convex cell complex whose union is R n . Connectedness in Euclidean n-space is usually modeled by graph-theoretic notions of connectedness derived from adjacency relations defined on the grid points or n-cells.

For commonly used grids and complexes in the cases n = 2 and 3, certain pairs of adjacency relations (κ, λ) on the grid points or n-cells are known to be "good pairs." For these pairs of relations (κ, λ), many results of digital topology concerning a set of grid points or n-cells and its complement have versions in which κ-adjacency is used to define connectedness on the set and λ-adjacency is used to define connectedness on its complement.

For example, [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF] and [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Herman | Oriented surfaces in digital spaces[END_REF] are good pairs of adjacency relations6 on Z 2 . Thus Rosenfeld's digital Jordan curve theorem [START_REF] Rosenfeld | Arcs and curves in digital pictures[END_REF] is valid when one of 4-and 8-adjacency is used to define the sense in which a digital simple closed curve is connected and the other of the two adjacency relations is used to define connected components of the digital curve's complement. The theorem is not valid if the same one of 4-or 8-adjacency is used for both purposes: [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Herman | Oriented surfaces in digital spaces[END_REF] and [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF] are not good pairs on Z 2 . However, there are some adjacency relations that form good pairs with themselves. An example of such a good pair is the pair [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] on the grid points of a 2D hexagonal grid. (The grid points are the centers of the hexagons in a tiling of the Euclidean plane by regular hexagons, and two points are 6-adjacent if they are the centers of hexagons that share an edge.) Another example is the good pair (κ 2 , κ 2 ) on Z 2 , where κ 2 is Khalimsky's adjacency relation [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] on Z 2 , which is defined as follows: Say that a point of Z 2 is pure if its coordinates are both even or both odd, and mixed otherwise. Then two points of Z 2 are κ 2 -adjacent if they are 4-adjacent, or if they are both pure points and are 8-adjacent. (See Examples 2.9 and 2.10 below for diagrams that show the two adjacency relations discussed in this paragraph.)

In three dimensions, [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF]26), (26,[START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF]18), (18,[START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] are good pairs of adjacency relations on Z 3 . A different example of a good pair on Z 3 is (κ 3 , κ 3 ), where κ 3 is the 3D analog of κ 2 : Two points of Z 3 are κ 3 -adjacent if they are 6-adjacent, or if they are 26-adjacent and at least one of the two is a pure point, where a pure point is a point whose coordinates are all odd or all even. [START_REF] Rosenfeld | Arcs and curves in digital pictures[END_REF][START_REF] Rosenfeld | Arcs and curves in digital pictures[END_REF], [START_REF] Rosenfeld | Arcs and curves in digital pictures[END_REF]18), and (18, 12) are good pairs of adjacency relations on the points of a 3D face-centered cubic grid (e.g., on {(x, y, z) ∈ Z 3 | x + y + z ≡ 0(mod 2)}) and (14, 14) is a good pair on the points of a 3D body-centered cubic grid (e.g., on {(x, y, z) ∈ Z 3 | x ≡ y ≡ z(mod 2)}).

At present, when results of 2D and 3D digital topology are proved using discrete methods, they are often proved for one good pair of adjacency relations at a time, and the details of the proof may be significantly different for different good pairs. 7 In the case of 3D grids, even if we consider only the nine good pairs of adjacency relations mentioned above, a result such as a digital Jordan surface theorem may have up to nine different versions! This state of affairs seems to us to be unsatisfactory. We have begun to consider an alternative approach to digital topology, in which "well-behaved" digital spaces are defined axiomatically, using axioms that are general enough to admit digital spaces which correspond to the good pairs of adjacency relations mentioned above. This approach allows a result of 2D or 3D digital topology to be proved as a single theorem for all well-behaved spaces that satisfy appropriate hypotheses. (Our Jordan curve theorem, Theorem 4.8 below, illustrates this.)

In this paper we confine our attention to digital spaces that model subsets of the Euclidean plane and other surfaces. We give an axiomatic definition of a very general class of such spaces, which includes spaces corresponding to all of the good pairs of adjacency relations that have been used in the literature on 2D digital topology (both in the plane and on boundary surfaces). A space that satisfies our axiomatic definition is called a gads. As will be seen in Section 2.5, a substantial part of the mathematical framework used in our definition of a gads has previously been used by the third author [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Herman | Geometry of digital spaces[END_REF].

As first steps in the development of digital topology for these spaces, we define the intersection number of two paths on a gads, and outline a proof that the number is invariant under homotopic deformation of the two paths. This is mostly a generalization, to arbitrary gads, of definitions and theorems given by the first author and Malgouyres in [START_REF] Fourey | Intersection number of paths lying on a digital surface and a new Jordan theorem[END_REF][START_REF] Fourey | Intersection number and topology preservation within digital surfaces[END_REF]. We also give a (discrete) definition of planar gads, which model subsets of the Euclidean plane, and present a Jordan curve theorem for such gads. In contrast to some earlier work by the second author (e.g., [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Kong | Polyhedral analogs of locally finite topological spaces[END_REF][START_REF] Kong | Concepts of digital topology[END_REF]), this paper does not use any arguments that are based on polyhedral continuous analogs of digital spaces, but uses only discrete arguments. 7 There has been work on digital topology that deals with substantial classes of adjacency relations in a unified way. But most of this work depends on the construction of continuous analogs of sets of grid points and the use of arguments and results of continuous topology (such as the Jordan curve theorem for the Euclidean plane). For examples, see [START_REF] Kong | Polyhedral analogs of locally finite topological spaces[END_REF][START_REF] Kong | Concepts of digital topology[END_REF][START_REF] Neumann-Lara | Digital jordan curves -a graph-theoretical approach to a topological theorem[END_REF].

GADS and pGADS

Basic Concepts and Notations

For any set P we denote by P {2} the set of all unordered pairs of distinct elements of P (equivalently, the set of all subsets of P with exactly two elements). Let P be any set and let ρ ⊆ P {2} . 8 Two elements a and b of P [respectively, two subsets A and B of P ] are said to be ρ-adjacent if {a, b} ∈ ρ [respectively, if there exist a ∈ A and b ∈ B with {a, b} ∈ ρ]. Similarly, if a ∈ P and B ⊆ P then we say that a and B are ρ-adjacent if there is some b in B such that {a, b} ∈ ρ. If x ∈ P we denote by N * ρ (x) the set of elements of P which are ρ-adjacent to x; these elements are also called the ρ-neighbors of x. We call N * ρ (x) the punctured ρ-neighborhood of x. A ρ-path from a ∈ P to b ∈ P is a finite sequence (x 0 , . . . , x l ) of one or more elements of P such that x 0 = a, x l = b and, for all i ∈ {0, . . . , l -1}, {x i , x i+1 } ∈ ρ. The nonnegative integer l is the length of the path. A ρ-path of length 0 is called a one-point path. For all integers m, n, 0 ≤ m ≤ n ≤ l, the subsequence (x m , . . . , x n ) of (x 0 , . . . , x l ) is called an interval or segment of the path. For all i ∈ {1, . . . , l} we say that the elements x i-1 and x i are consecutive on the path, and also that x i-1 precedes x i and x i follows x i-1 on the path. Note that consecutive elements of a ρ-path can never be equal.

A ρ-path (x 0 , . . . , x l ) is said to be simple if x i ̸ = x j for all distinct i and j in {0, . . . , l}. It is said to be closed if x 0 = x l , so that x 0 follows x l-1 . It is called a ρ-cycle if it is closed and x i ̸ = x j for all distinct i and j in {1, . . . , l}. One-point paths are the simplest ρ-cycles. Two ρ-cycles c 1 = (x 0 , . . . , x l ) and c 2 = (y 0 , . . . , y l ) are said to be equivalent if there exists an integer k, 0 ≤ k ≤ l -1, such that x i = y (i+k) mod l for all i ∈ {0, . . . , l}.

If S ⊆ P , two elements a and b of S are said to be ρ-connected in S if there exists a ρ-path from a to b that consists only of elements of S. ρ-connectedness in S is an equivalence relation on S; its equivalence classes are called the ρcomponents of S. The set S is said to be ρ-connected if there is just one ρ-component of S.

Given two sequences c 1 = (x 0 , . . . , x m ) and c 2 = (y 0 , . . . , y n ) such that x m = y 0 , we denote by c 1 .c 2 the sequence (x 0 , . . . , x m , y 1 , . . . , y n ), which we call the catenation of c 1 and c 2 . Whenever we use the notation c 1 .c 2 , we are also implicitly saying that the last element of c 1 is the same as the first element of c 2 . It is clear that if c 1 and c 2 are ρ-paths of lengths l 1 and l 2 , then c 1 .c 2 is a ρ-path of length l 1 + l 2 .

For any sequence c = (x 0 , . . . , x m ), the reverse of c, denoted by c -1 , is the sequence (y 0 , . . . , y m ) such that y k = x m-k for all k ∈ {0, . . . , m}. It is clear that if c is a ρ-path of length l then so is c -1 .

A simple closed ρ-curve is a nonempty finite ρ-connected set C such that each element of C has exactly two ρ-neighbors in C. (Note that a simple closed ρcurve must have at least three elements.) A ρ-cycle of length |C| that contains every element of a simple closed ρ-curve C is called a ρ-parameterization of C. Note that if c and c ′ are ρ-parameterizations of a simple closed ρ-curve C, then c ′ is equivalent to c or to c -1 .

If x and y are ρ-adjacent elements of a simple closed ρ-curve C, then we say that x and y are ρ-consecutive on C. If x and y are distinct elements of a simple closed ρ-curve C that are not ρ-consecutive on C, then each of the two ρ-components of C \ {x, y} is called a ρ-cut-interval (of C) associated with x and y.

The following is a rather trivial but important consequence of our definition of a simple closed ρ-curve:

Property 2.1 If σ ⊆ ρ ⊆ P {2} , and C ρ is a simple closed ρ-curve that con- tains a simple closed σ-curve C σ , then C ρ = C σ .

Definition of a gads

We first introduce the notion of a 2D digital complex. Every gads has a 2D digital complex as an underlying structure. In fact, we shall see in Definition 2.3 that a gads is just a 2D digital complex equipped with a pair of adjacency relations (on the vertices of the complex) that satisfy three simple axioms. Definition 2.2 (2D digital complex) A 2D digital complex is an ordered triple (V, π, L), where • V is a set whose elements are called vertices or spels (short for spatial elements), • π ⊆ V {2} , and the pairs of vertices in π are called proto-edges, • L is a set of simple closed π-curves whose members are called loops, and the following four conditions hold:

(1) V is π-connected and contains more than one vertex.

(2) For any two distinct loops L 1 and L 2 , L 1 ∩ L 2 is either empty, or consists of a single vertex, or is a proto-edge. [START_REF] Fourey | Intersection number and topology preservation within digital surfaces[END_REF] No proto-edge is included in more than two loops. [START_REF] Herman | Oriented surfaces in digital spaces[END_REF] Each vertex belongs to only a finite number of proto-edges.

A positive integer k (such as 4, 8, or 6) may be used to denote the set of all unordered pairs of k-adjacent vertices. We write L 2×2 to denote the set of all 2 × 2 squares in Z 2 . With this notation, the triple (Z 2 , 4, L 2×2 ) is a simple example of a 2D digital complex, which can be used to illustrate and motivate the conditions of Definition 2.2. Since Z 2 is 4-connected and has infinitely many points, condition (1) holds. As required by condition (2), the intersection of two 2 × 2 squares is either empty, or consists of a single point, or is a pair of 4-adjacent points. Moreover, each pair of 4-adjacent points is contained in just two 2 × 2 squares of Z 2 , and so condition (3) holds. Finally, each point of Z 2 is 4-adjacent to just 4 other points of Z 2 , and so condition (4) holds too.

Definition 2.3 (GADS)

A generic axiomatized digital surface-structure, or gads, is a pair G = ((V, π, L), (κ, λ)) where (V, π, L) is a 2D digital complex (whose vertices, proto-edges and loops are also referred to as vertices, protoedges and loops of G) and where κ and λ are subsets of V {2} that satisfy Axioms 1, 2, and 3 below. The pairs of vertices in κ and λ are called κ-edges and λ-edges, respectively. Axiom 1 Every proto-edge is both a κ-edge and a λ-edge: π ⊆ κ ∩ λ.

Axiom 2

For all e ∈ (κ ∪ λ) \ π, some loop contains both vertices of e.

Axiom 3 If x, y ∈ L ∈ L, but x and y are not π-consecutive on L, then (a) {x, y} is a λ-edge if and only if L \ {x, y} is not κ-connected. (b) {x, y} is a κ-edge if and only if L \ {x, y} is not λ-connected.
A gads is said to be finite if it has finitely many vertices; otherwise it is said to be infinite. (V, π, L) is called the underlying complex of G.

Axiom 2 ensures that the adjacency relations κ and λ are "local" with respect to the set of loops. Note also that if e ∈ (κ ∪ λ) \ π (i.e., e is a κ-or λ-edge that is not a proto-edge) then there can only be one loop that contains both vertices of e, by condition [START_REF] Fourey | Intersection number of paths lying on a digital surface and a new Jordan theorem[END_REF] in the definition of a 2D digital complex.

In Axiom 3, note that L \ {x, y} is κ-(λ-)connected if and only if some vertex in one of the two π-cut-intervals of L associated with x and y is κ-(λ-)adjacent to some vertex in the other π-cut-interval. This axiom is needed because we commonly use one of the adjacency relations κ and λ on a set S of vertices and the other of κ and λ on its complement V \ S. Because of the "only if" parts of Axiom 3, the very definition of a gads excludes a well known kind of "topological paradox" that occurs in bad digital spaces, in which a path in S "crosses" a path in V \S. The "if" parts of Axiom 3 exclude another well known kind of topological paradox that occurs in bad digital spaces, in which a set S of isolated vertices separates its complement V \ S into two or more components. As illustrations of Axiom 3, observe that both ((Z 2 , 4, L 2×2 ), [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF]) and ((Z 2 , 4, L 2×2 ), [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Herman | Oriented surfaces in digital spaces[END_REF]) satisfy Axiom 3, but ((Z 2 , 4, L 2×2 ), (4, 4)) violates the "if" parts of the axiom, while ((Z 2 , 4, L 2×2 ), [START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF]) violates the "only if" parts of the axiom.

A question raised by Definition 2.3 is why we use three adjacency relations κ, λ, and π when pairs of adjacency relations have been used in most previous work on digital topology. Indeed, for most of the gads we use to represent digital spaces that have been considered by previous authors, our proto-adjacency π is the same relation as one (or both) of the adjacency relations κ and λ. But the mathematical role of π is different and in a sense more fundamental than the roles of κ and λ. For example, the definitions of some basic topological properties of gads-notably simple connectedness, orientability, planarity, and the Euler characteristic-are independent of κ and λ, and depend only on π and the set of loops. By distinguishing π from κ and λ we not only make our theory more general but, more significantly, also clarify its logical structure.

Another benefit of distinguishing π from κ and λ is that it allows our definition of a gads to be symmetrical with respect to κ and λ:

Property 2.4 If ((V, π, L), (κ, λ)) is a gads then ((V, π, L), (λ, κ)
) is also a gads. So any statement which is true of every gads ((V, π, L), (κ, λ)) remains true when κ is replaced by λ and λ by κ.

The set of all gads can be ordered as follows:

Definition 2.5 (⊆ order, subGADS) Let G = ((V, π, L), (κ, λ)) and G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )) be gads such that • V ⊆ V ′ , π ⊆ π ′ and L ⊆ L ′ . • For all L ∈ L, κ ∩ L {2} = κ ′ ∩ L {2} and λ ∩ L {2} = λ ′ ∩ L {2} .
Then we write G ⊆ G ′ and say that G is a subGADS of G ′ . We also refer to G as the subGADS of G ′ induced by (V, π, L). We write

G ⊊ G ′ to mean G ⊆ G ′ and G ̸ = G ′ . We write G < G ′ to mean G ⊊ G ′ and L ̸ = L ′ .
As an immediate consequence of this definition and Axioms 1 and 2, we have:

Property 2.6 If G = ((V, π, L), (κ, λ)) and G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )) are two gads such that G ⊆ G ′ , then κ ⊆ κ ′ and λ ⊆ λ ′ .

Interior Vertices and pgads

We are particularly interested in those gads that model a surface without boundary, and call any such gads a pgads:

Definition 2.7 (pGADS) A pgads is a gads in which every proto-edge is included in two loops.

The p in pgads stands for pseudomanifold : A finite pgads that is strongly connected -see Section 2.4-models a 2-dimensional pseudomanifold (as defined for example in [1, Part 2, §3]). More informally, we can say that a finite pgads models a "closed surface that may have topological singularities." (By a singularity we mean a point whose removal would locally disconnect the surface. For example, if we deform a spherical surface by bringing two distinct points a and a ′ together so they coincide at a single point a * , then the resulting "pinched sphere" has a singularity at a * .) A pgads that models the Euclidean plane must be infinite.

A vertex v of a gads G is called an interior vertex of G if every proto-edge of G that contains v is included in two loops of G. It follows that a gads G is a pgads if and only if every vertex of G is an interior vertex.

Below are pictures of some pgads.

Example 2.8 Z 2 with the 4-and 8-adjacency relations

G = ((Z 2 , κ, L 2×2 ), (κ, λ)) κ = 4 (not shown), λ = 8.
Example 2.9 Z 2 with Khalimsky's adjacency relation

G = ((Z 2 , 4, L 2×2 ), (κ 2 , κ 2 ))
, where κ 2 consists of all unordered pairs of 4-adjacent points and all unordered pairs of 8-adjacent pure points.

Example 2.10 The hexagonal grid with the 6-adjacency relation

G = ((H, 6, L), (6, 6)) H = {(i + j 2 , j √ 3 2 ) ∈ R 2 | i, j ∈ Z } L = {{p, q, r} ⊂ H | dst(p, q) = dst(q, r) = dst(p, r) = 1} dst(x,
G = ((V, κ, L), (κ, λ)) V = {a, b, c, d, e, f, g, h, i} κ = {{a, b}, {b, c}, {c, a}, {d, f }, {f, g}, {g, d}, {e, h}, {h, i}, {i, e}, {b, f }, {c, g}, {a, d}, {f, h}, {g, i}, {d, e}, {h, b}, {i, c}, {e, a}} λ = {{x, y} | ∃L ∈ L, x, y ∈ L} (not shown) L = {{a, b, f, d}, {d, f, h, e}, {e, h, b, a}, {b, c, g, f }, {f, g, i, h}, {h, i, c, b}, {c, a, d, g}, {g, d, e, i}, {i, e, a, c}}

Strong Connectedness and Singularities

Let G = ((V, π, L), (κ, λ)) be a gads. Two loops L and L ′ of G are said to be adjacent if L ∩ L ′ is a proto-edge of G. A subset L ′ of L is said to be strongly connected if for every pair of loops L and L ′ in L ′ there exists a sequence L 0 , . . . , L n of loops in L ′ such that L 0 = L, L n = L ′ and, for all i ∈ {0, . . . , n -1}, L i and L i+1 are adjacent. G is said to be strongly connected if L is strongly connected. (Note that whether or not G is strongly connected depends only on the underlying complex of G.)

A vertex x of G is said to be a singularity of G if the set of all loops of G that contain x is not strongly connected. Vertices that are not singularities are said to be nonsingular. (Again, whether or not x is a singularity of G depends only on the underlying complex of G.)

Even a strongly connected pgads may have a singularity. For example, the "strangled torus" pgads obtained from the torus-like pgads of Example 2.11 above by identifying the vertices a, b, and c has a singularity at a = b = c but is strongly connected.

Relationship to the Mathematical Framework of [4,5]

Here we briefly discuss the relationship between our concept of a gads and digital structures previously studied by the third author in [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Herman | Geometry of digital spaces[END_REF].

If ((V, π, L), (κ, λ)) is a gads, then, in the terminology of [START_REF] Herman | Geometry of digital spaces[END_REF], (V, π) is a digital space, π is the proto-adjacency of that space, and each of κ and λ is a speladjacency of the space. The principal new ingredients in our concept of a gads are the set of loops L and Axioms 2 and 3. In a gads ((V, π, L), (κ, λ)) with the property that every π-cycle of length 4 is a loop of the gads, the "if" parts of Axiom 3 make {κ, λ} a normal pair of spel-adjacencies.

An important difference between our theory and that of [START_REF] Herman | Oriented surfaces in digital spaces[END_REF][START_REF] Herman | Geometry of digital spaces[END_REF] is that our theory is restricted to spaces that model subsets of surfaces (though only because of condition (3) in the definition of a 2D digital complex).

Relationship to the Mathematical Framework of [13]

What we have called a 2D digital complex is similar to the concept of an oriented neighborhood structure considered by Voss and Klette [START_REF] Klette | The three basic formulas of oriented graphs[END_REF][START_REF] Voss | Discrete images, objects, and functions in Z n[END_REF]. In fact, the underlying complex of any orientable 9 pgads can be regarded as an oriented neighborhood structure. The loops of our complex would then correspond to the meshes (Voss's term) of the oriented neighborhood structure. A minor difference between our and Voss's theories is that whereas in our work the set of loops is a primitive component of a 2D digital complex, in Voss's theory the set of meshes is not a primitive component of an oriented neighborhood structure. Instead, Voss uses a set of cyclic orderings of the neighborhoods of the vertices as a primitive component, and defines the meshes in terms of these cyclic orderings (which roughly correspond to the cycles N * Ω,y (x) we define in Section 5.2).

A much more significant difference between Voss's theory (as developed in [START_REF] Voss | Discrete images, objects, and functions in Z n[END_REF]) 9 Orientability is defined in Section 5.1.

and ours is that in his theory there are no analogs of the adjacency relations κ and λ of our gads. A consequence of this is that some results of our theory, such as our Jordan curve theorem for planar gads (Theorem 4.8), cannot be conveniently stated purely in terms of the concepts introduced in [START_REF] Voss | Discrete images, objects, and functions in Z n[END_REF].

There is an interesting separation theorem for planar oriented neighborhood structures in [START_REF] Voss | Discrete images, objects, and functions in Z n[END_REF], 10 but it is quite different from our Jordan curve theorem. For example, while Voss's result implies that the complement of a curve satisfying his hypothesis has at least two components, the complement of such a curve may have more than two components. In contrast, a curve that satisfies the hypotheses of our Jordan curve theorem separates its complement into exactly two components, as a (continuous) Jordan curve does in the Euclidean plane. Moreover, the hypothesis on the curve in Voss's theorem (that it be a "border mesh" of some substructure) is global, whereas the hypotheses on the simple closed curve in our Jordan curve theorem are purely local.

Homotopic Paths and Simple Connectedness

In this section G = ((V, π, L), (κ, λ)) is a gads, ρ satisfies π ⊆ ρ ⊆ κ ∪ λ, and X is a ρ-connected subset of V . (We are mainly interested in the cases where ρ = κ, λ, or π.)

Loosely speaking, two ρ-paths in X with the same initial and the same final vertices are said to be ρ-homotopic within X in G if one of the paths can be transformed into the other by a sequence of small local deformations within X. The initial and final vertices of the path must remain fixed throughout the deformation process. The next two definitions make this notion precise. Definition 3.1 (elementary G-deformation) Two finite vertex sequences c and c ′ of G with the same initial and the same final vertices are said to be the same up to an elementary G-deformation if there exist vertex sequences c 1 , c 2 , γ, and γ ′ such that c = c 1 .γ.c 2 , c ′ = c 1 .γ ′ .c 2 , and either there is a loop of G that contains all of the vertices in γ and γ ′ , or there is a proto-edge {x, y} for which one of γ and γ ′ is (x) and the other is (x, y, x).

Informally, we refer to any ρ-path of the form (x, y, x) as a ρ-back-and-forth. Significantly, ρ-homotopic paths can also be characterized in terms of certain special types of elementary G-deformation, as the next proposition will show. We first define the allowed types of deformation, which include only the insertion or removal of either a ρ-back-and-forth or a ρ-parameterization of a simple closed ρ-curve in a loop of G: Definition 3.3 (minimal ρ-deformation) Two ρ-paths c and c ′ with the same initial and the same final vertices are said to be the same up to a minimal ρ-deformation in G if there exist ρ-paths c 1 , c 2 , and γ such that one of c and c ′ is c 1 .γ.c 2 , the other is c 1 .c 2 , and either γ = (x, y, x) for some ρ-edge {x, y} or γ is a ρ-parameterization of a simple closed ρ-curve contained in a loop of G.

This concept of deformation is particularly simple when ρ = π, because a simple closed ρ-curve contained in a loop of G must then be the whole of a loop of G (by Property 2.1, since a loop of G is a simple closed π-curve).

Say that two ρ-paths c and c ′ in a set X with the same initial and the same final vertices are strongly ρ-homotopic within X in G if there exists a sequence of ρ-paths c 0 , . . . , c n in X such that c 0 = c, c n = c ′ and, for 0 ≤ i ≤ n-1, c i and c i+1 are the same up to a minimal ρ-deformation. The next proposition states that ρ-paths are strongly ρ-homotopic if and only if they are ρ-homotopic. As a minimal ρ-deformation is a much more restrictive concept than an elementary G-deformation, this fact is frequently useful in proofs. It allows us to show that a property of ρ-paths is invariant under ρ-homotopy just by verifying that the property's value is unchanged by (1) insertion of a ρ-back-and-forth, and (2) insertion of a ρ-parameterization of a simple closed ρ-curve contained in a loop of G. Proposition 3.4 Two ρ-paths in X that have the same initial and the same final vertices are strongly ρ-homotopic within X in G if and only if they are ρ-homotopic within X in G.

Proof: Let E and M be infix binary relation symbols 11 that respectively denote the restrictions to ρ-paths in X of the relations "are the same up to an elementary G-deformation" and "are the same up to a minimal ρ-deformation in G." We need to show that the transitive closures of E and M are the same.

Our proof will depend on the following two facts, which are evident from the definition of M . (Here (x) denotes the one-point path whose only vertex is x, and the infix relation symbol M ∞ denotes M 's transitive closure.)

A. If γ and γ ′ are ρ-paths in X that respectively end and begin at the vertex x, and

c is a closed ρ-path in X such that c M ∞ (x), then γ.c.γ ′ M ∞ γ.γ ′ . B. If γ is a ρ-path in X whose initial vertex is x, then γ.γ -1 M ∞ (x).
Note that since the E relation contains the M relation, E's transitive closure contains M 's transitive closure. It remains to show that M 's transitive closure contains E (and hence, being transitive, also contains E's transitive closure). As a first step, we establish the following special case of this:

Claim: If c is a closed ρ-path in X that begins and ends at a vertex x, and all the vertices of c are contained in a loop of G, then c M ∞ (x). Indeed, suppose the Claim is false and c is a shortest counterexample. Then c's length exceeds 2, and c is not a parameterization of any simple closed ρ-curve (for otherwise c satisfies the Claim, by the definition of M ).

Let c = (x 0 , x 1 , x 2 , . . . , x k = x 0 ). For 0 ≤ i ≤ j ≤ k, let c i,j denote the contiguous subsequence (x i , . . . , x j ) of c. (Thus c 0,k = c, and c i,i is a one-point path for 0 ≤ i ≤ k.) Suppose c is not a ρ-cycle. Then c j,j ′ is a closed ρ-path for some j and j ′ such that 1 ≤ j < j ′ ≤ k. Since c is a shortest counterexample, c j,j ′ satisfies the Claim, and so c j,j ′ M ∞ (x j ). Hence (by fact A) c = c 0,j .c j,j ′ .c j ′ ,k M ∞ c 0,j .c j ′ ,k . Again, c 0,j .c j ′ ,k is shorter than the shortest counterexample c and therefore satisfies the Claim. Hence c 0,j .c j ′ ,k M ∞ (x 0 ) and so (by the transitivity of M ∞ ) we have c M ∞ (x 0 ), which contradicts our assumption that c is a counterexample to the Claim. Hence c is a ρ-cycle.

As c is not a parameterization of a simple closed ρ-curve, x j is ρ-adjacent to x j ′ for some j and j ′ such that j < j ′ and j ′ -j ̸ = k -1. Therefore

c = c 0,j ′ .c j ′ ,k M c 0,j ′ .(x j ′ , x j , x j ′ ).c j ′ ,k = c 0,j .c ′ .(x j , x j ′ ).c j ′ ,k (1)
where c ′ is the closed ρ-path c j,j ′ .(x j ′ , x j ). As c ′ is shorter than the shortest counterexample c, it satisfies the Claim and so c ′ M ∞ (x j ). Hence (by fact A)

c 0,j .c ′ .(x j , x j ′ ).c j ′ ,k M ∞ c 0,j .(x j , x j ′ ).c j ′ ,k (2)
Again, since c 0,j .(x j , x j ′ ).c j ′ ,k is shorter than the shortest counterexample c, it satisfies the Claim and so c 0,j .(x j , x j ′ ).c j ′ ,k M ∞ (x 0 ). This, (1), and (2) imply that c M ∞ (x 0 ), which contradicts our assumption that c is a counterexample to the Claim. This contradiction establishes the Claim.

To complete the proof that M ∞ contains E, let u and v be two ρ-paths in X such that u E v. We need to show that u M ∞ v. By the definition of E there exist c 1 , c 2 , γ, and

γ ′ such that u = c 1 .γ.c 2 , v = c 1 .γ ′ .c 2 ,
and either (a) there is a proto-edge {x, y} for which one of γ and γ ′ is (x) and the other is (x, y, x), or (b) there is a loop of G that contains all of the vertices in γ and γ ′ . In case (a), u M v and we are done. In case (b), the Claim implies that γ -1 .γ ′ M ∞ (x), where x is the final vertex of γ and γ ′ (and the initial vertex of c 2 ). So (by facts A and B) u

= c 1 .γ.c 2 M ∞ c 1 .γ.γ -1 .γ ′ .c 2 M ∞ c 1 .γ ′ .c 2 = v as required. 2
The next two definitions give a precise meaning to our concept of a simply connected gads. Whether or not a gads is simply connected will depend only on its underlying complex.

Definition 3.5 (reducible closed path) Let c = (x 0 , . . . , x n ) be a closed ρ-path in X (so x n = x 0 ). Then c is said to be ρ-reducible within X in G if c and the one-point path

(x 0 ) are ρ-homotopic within X in G. We say c is ρ-reducible in G if c is ρ-reducible within V in G.

Definition 3.6 (simple connectedness)

The set X is said to be ρ-simply

connected in G if every closed ρ-path in X is ρ-reducible within X in G. The gads G is said to be simply connected if V is π-simply connected in G.
A significant consequence of these definitions is that V is ρ-simply connected in G if and only if V is π-simply connected in G (i.e., G is simply connected). This is because there is a natural bijection of the ρ-homotopy classes of G onto the π-homotopy classes of G. Indeed, for each pair (x, y) of ρ-adjacent vertices, let p x,y be a π-path from x to y with the following properties:

• If {x, y} is a π-edge, then p x,y = (x, y).

• Otherwise, p x,y is a π-path from x to y in the loop of G that contains the ρ-edge {x, y}.

(Note that p x,y and (x, y) are the same up to an elementary G-deformation.)

For each ρ-path c = (x 0 , x 1 , . . . , x n ), we now define p c to be the π-path p x 0 ,x 1 . p x 1 ,x 2 . . . . . p x n-1 ,xn . Then it is readily confirmed that:

(1) For all π-paths c, p c = c.

(2) For all ρ-paths c, the paths c and p c are ρ-homotopic.

(3) For any two ρ-paths c ′ and c ′′ that are the same up to an elementary G-deformation, the π-paths p c ′ and p c ′′ are the same up to an elementary G-deformation.

By (3), the map c → p c induces a well-defined map of ρ-homotopy classes of G to π-homotopy classes of G. By (1), this induced map is onto. It follows from (2) that the map is one-to-one. Hence the map is a bijection.

Although the concepts of ρ-simple connectedness and π-simple connectedness are equivalent when applied to the entire set of vertices of G, ρ-simple connectedness is in general a stronger property than π-simple connectedness: While it can be shown that if X is ρ-simply connected in G then X is also π-simply connected in G, the converse is false in general. 12The final result in this section gives a useful sufficient condition for a gads to have no singularities: Proposition 3.7 Let G be a gads that is simply connected and strongly connected. Then G has no singularities.

Proof: Let G = ((V, π, L), (κ, λ)) and suppose x is a singularity of G. Then there exist two nonempty sets of loops of G, α 1 = {L 1 , . . . , L i } and α 2 = {L i+1 , . . . , L l }, such that {L 1 , . . . , L l } is the set of all loops of G that contain x, and such that L ∩ L ′ = {x} for all L in α 1 and L ′ in α 2 .

For any π-path c = (c 0 , c 1 , . . . , c n ), let ν(c, x) be the number of pairs (c i , c i+1 ) for which c i belongs to a loop in α 1 and c i+1 = x, minus the number of pairs (c i , c i+1 ) for which c i = x and c i+1 belongs to a loop in α 1 . If γ is a π-backand-forth, then, plainly, ν(γ, x) = 0. If γ is a π-parameterization of a simple closed π-curve that is contained in a loop L of G (in which case γ must actually be a π-parameterization of L), then either L does not contain x, or L ∈ α 1 , or L ∈ α 2 ; in each case it is evident that ν(γ, x) = 0. It follows that if two π-paths c ′ and c ′′ are the same up to a minimal π-deformation in G, then ν(c ′ , x) = ν(c ′′ , x). Hence (by Proposition 3.4), ν(c ′ , x) = ν(c ′′ , x) whenever c ′ and c ′′ are π-homotopic in G. But G is simply connected, and ν(c, x) = 0 when c is a one-point path. Hence ν(c, x) = 0 for every closed π-path c. Now let y be a π-neighbor of x that belongs to a loop in α 1 , and let z be a π-neighbor of x that belongs to a loop in α 2 . Since G is strongly connected, there must be a π-path c ′ from z to y that does not contain x. But the closed π-path c = (x, z).c ′ .(y, x) would satisfy ν(c, x) = 1, a contradiction. 2

Planar GADS and a Jordan Curve Theorem

In this section we define a class of gads that are discrete models of subsets of the Euclidean plane. The definition depends on two concepts which we now present: Note that the Euler characteristic of a gads depends only on its underlying complex, and that it is not defined for an infinite gads.

Definition 4.2 (limit of an increasing GADS sequence)

For all i ∈ N let G i = ((V i , π i , L i ), (κ i , λ i )) be a gads and let G 0 ⊆ G 1 ⊆ G 2 ⊆ . . .. Then ∪ i∈N G i denotes (( ∪ i∈N V i , ∪ i∈N π i , ∪ i∈N L i ), ( ∪ i∈N κ i , ∪ i∈N λ i )).

(By Definition 2.5 and Property 2.6, this is a gads if each element of

∪ i∈N V i is contained in only finitely many distinct members of ∪ i∈N π i .)
We are now in a position to define a planar gads. Whether or not a gads is planar depends only on its underlying complex, as can be deduced quite easily from the following definition.

Definition 4.3 (planar GADS)

A pgads PG is said to be planar if PG = ∪ i∈N G i for some infinite sequence of finite gads G 0 < G 1 < G 2 < . . . such that G i is strongly connected and χ(G i ) = 1 for all i ∈ N. A gads G is said to be planar if there exists a planar pgads PG such that G ⊆ PG.

Remark 4.4 Definition 4.3 is based on the idea of regarding a plane as the limit of a sequence of increasingly large closed topological disks. (Note that the Euler characteristic of a closed topological disk is 1.)

From the above definition it is evident that all planar pgads are infinite and strongly connected. A somewhat less obvious consequence of the definition of planar pgads is that they are all simply connected. This will follow from: Proposition 4.5 Let G be a strongly connected gads and let G ′ be a finite gads such that G ′ < G and χ(G ′ ) = 1. Then G ′ is simply connected.

Sketch of proof:

Let G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )). If L ′ = ∅, then |V ′ |-|π ′ | = 1 (since χ(G ′ ) = 1
) and so (V ′ , π ′ ) is a tree. In this case the result is easily proved by induction on the number of proto-edges. To prove the result in the case where G ′ has at least one loop, we use induction on the number of loops. [The induction step is based on the easily established fact that, since G ′ < G and G is strongly connected, there must exist a proto-edge e of G ′ that belongs to just one loop of G ′ , L say. Readily, G ′ is simply connected if the subGADS of G induced by (V ′ , π ′ \ {e}, L ′ \ {L}) is simply connected.] 2 Corollary 4.6 A planar pgads is simply connected.

Proof: Let PG = ((V * , π * , L * ), (κ * , λ * )) be a planar pgads, and suppose c * is a closed π * -path. By the definition of a planar pgads, there exists a gads G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )) which satisfies the hypotheses of the above proposition when G = PG, such that c * is a π ′ -path of G ′ . Since G ′ is simply connected, c * is π ′ -reducible in G ′ , and so c * is also π * -reducible in PG. 2

As a consequence of this corollary and Proposition 3.7, we deduce: Proposition 4.7 A planar pgads has no singularities.

The next theorem is our main result concerning planar gads. It generalizes Rosenfeld's digital Jordan curve theorem [START_REF] Rosenfeld | Arcs and curves in digital pictures[END_REF] (for Z 2 with (4,8) or (8,4) adjacencies) to every planar gads. We will outline a proof of this theorem in Section 8. V,π,L),(κ,λ)) be a planar gads. Let C be a simple closed κ-curve that is not included in any loop of PG, and which consists entirely of interior vertices of PG. Then V \ C has exactly two λ-components, and, for each vertex x ∈ C, N * λ (x) intersects both λ-components of V \ C.

Local Orientations and Orientability

We now introduce the notion of orientability in the context of GADS. The proof of Theorem 4.8 will use a more general theorem stated for orientable gads. We also establish, in Section 5.3, a link between simple connectedness and orientability.

Definitions

Let L 1 and L 2 be adjacent loops of a gads G = ((V, π, L), (κ, λ)) and let {x, y} = L 1 ∩ L 2 . Then π-parameterizations c 1 of L 1 and c 2 of L 2 are said to be coherent if x precedes y in one of c 1 and c 2 but x follows y in the other of c 1 and c 2 . A coherent π-orientation of a set of loops L ′ ⊆ L is a function Ω with domain L ′ such that:

(1) For each loop L in L ′ , Ω(L) is a π-parameterization of L.

(2) For all pairs of adjacent loops L and L ′ in L ′ , the π-parameterizations Ω(L) and Ω(L ′ ) of L and L ′ are coherent.

If such a function Ω exists, then we say L ′ is π-orientable. In this case two coherent π-orientations Ω 1 and Ω 2 of L ′ are said to be equivalent if, for every L in L ′ , Ω 1 (L) and Ω 2 (L) are equivalent π-parameterizations of L.

A coherent orientation of G is a coherent π-orientation of the set L of all loops of G. The gads G is said to be orientable if it has a coherent orientation (or, equivalently, if its set of loops is π-orientable). Evidently, if G ′ and G are gads such that G ′ ⊆ G and G is orientable, then G ′ is also orientable. Note that whether or not a gads is orientable depends only on its underlying complex.

It is easy to verify that the four pgads shown in Section 2.3 are all orientable. There is a simple non-orientable "Möbius-strip-like" gads whose underlying complex (V, π, L) has 6 vertices {a, b, c, d, e, f } and 3 loops, in which (d, a, b, e, d), (e, b, c, f, e), and (f, c, d, a, f ) are π-parameterizations of the loops.

The π-Cycles N * Ω,y (x) Around Nonsingular Interior Vertices x of an Orientable gads

Let G = ((V, π, L), (κ, λ)) be a (not necessarily orientable) gads, and let x be a nonsingular interior vertex of G.

A loop-circuit of G is a sequence (L 0 , . . . , L l-1 ) of three or more loops of G (so l ≥ 3) such that, for all i ∈ {0, . . . , l -1}, L i is adjacent to L (i+1) mod l . A loop-circuit of G at x is a loop-circuit of G that is an enumeration of the set of loops of G that contain x (with each of those loops occurring just once). Thus if (L 0 , . . . , L l-1 ) is a loop-circuit of G at x then, for each i ∈ {0, . . . l -1}, L i ∩ L (i+1) mod l is a proto-edge of G that contains x (by condition [START_REF] Fourey | Intersection number of paths lying on a digital surface and a new Jordan theorem[END_REF] in the definition of a 2D digital complex).

The set of loops of G that contain x is strongly connected (since x is nonsingular in G), and it is easy to show that each loop in the set is adjacent to exactly two others (since x is an interior vertex of G). Therefore a loop-circuit of G at x exists.

A coherent local orientation of G at x is a coherent π-orientation of the loops of G that contain x. Let Λ = (L 0 , . . . , L l-1 ) be a loop-circuit of G at x. Then the coherent local orientation of G at x induced by Λ, denoted by Ω Λ

x , is defined as follows. For 0 ≤ i ≤ l -1 let c i be a π-parameterization of L i that begins and ends at x, in which the second vertex is the vertex of L i ∩ L (i-1) mod l \ {x}, and the second-last vertex is the vertex of

L i ∩ L (i+1) mod l \ {x}. Then Ω Λ x is defined by Ω Λ x (L i ) = c i for 0 ≤ i ≤ l -1. Now let Ω ′ x be any coherent local orientation of G at x. Then Ω ′ x (L 0 ) is equiv- alent either to Ω Λ x (L 0 ) or to (Ω Λ x (L 0 )) -1 . It is readily confirmed that Ω ′ x must be equivalent to Ω Λ
x in the former case and to Ω (Λ -1 )

x in the latter case.

For any vertex v of G, the punctured loop neighborhood of v in G, denoted by N * L (v), is defined to be the union of all the loops of G which contain v, minus the vertex v itself.

Let Ω x be a coherent local orientation of G at x. For each vertex y of N * L (x), we now define a π-cycle N * Ωx,y (x) with the following properties: (1) The vertices of N * Ωx,y (x) are exactly the vertices of N * L (x). (2) N * Ωx,y (x) begins and ends at y. Let Λ = (L 0 , . . . , L l-1 ) be a loop-circuit of G at x such that Ω Λ

x is equivalent to Ω x . For i ∈ {0, . . . , l-1} let p i be the π-path obtained from Ω Λ

x (L i ) by removing its first and last vertices (both of which are the vertex x). Then we define N * Ωx,y (x) to be the π-cycle that is equivalent to the π-cycle p 0 . p 1 . . . . . p l-1 and which begins and ends at y. It is readily confirmed that this π-cycle is independent of our choice of the loop-circuit Λ (provided that Ω Λ

x is equivalent to Ω x ). The definition of N * Ωx,y (x) is illustrated by Figure 1. If G is orientable, and Ω is a coherent orientation of G, then we write N * Ω,y (x)

for N * Ωx,y (x), where Ω x is the coherent local orientation of G at x that is given by the restriction of Ω to the loops of G that contain x.

Simply Connected gads are Orientable

In this section we outline a proof of the following result: Proposition 5.1 Let G be a gads that is a subGADS of a simply connected gads. Then G is orientable.

Sketch of proof:

Let G = ((V, π, L), (κ, λ)) be a subGADS of the simply connected gads G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )
). Suppose G is not orientable. It is not hard to show that this implies G has a loop-circuit (L 0 , . . . , L l-1 ) whose set of loops is not π-orientable, such that no two L's are equal and, for all i, j ∈ {0, . . . , l-1}, L i is not adjacent to L j unless j = (i±1) mod l. (Intuitively, the loop circuit (L 0 , . . . , L l-1 ) "forms a Möbius strip.")

The idea now is to construct a π-path in ∪ 0≤i≤l-1 L i that cannot be π ′reducible in G ′ , and so contradict the simple connectedness of G ′ . For i ∈ {0, . . . , l -1}, let a i , b i ∈ V be vertices such that {a i , b i } is the π-edge that is shared by L i and L (i+1) mod l , and such that, for i ∈ {1, . . . , l -1}, a i-1 and a i belong to the same π-component of

L i \ {b i-1 , b i }. (It is possible that a i-1 = a i or b i-1 = b i .
) Then it is straightforward to verify that, since {L 0 , . . . , L l-1 } is not π-orientable, a l-1 and b 0 must belong to the same π-component of L 0 \{b l-1 , a 0 }. For i ∈ {1, . . . , l-1}, let c i be the simple π-path in L i \{b i-1 , b i } from a i-1 to a i . Also, let c l be the simple π-path in L 0 \ {b l-1 , a 0 } from a l-1 to b 0 . Let γ be the π-path c 1 . c 2 . . . . . c l . (b 0 , a 0 ).

Define the parity of a π ′ -path (x 0 , . . . , x n ) to be 0 or 1 according to whether an even or an odd number of terms in its sequence of π ′ -edges

({x i , x i+1 } | 0 ≤ i ≤ n -1) lie in the set {{a i , b i } | 0 ≤ i ≤ l -1}.
In view of the remark immediately following Definition 3.3, it is readily confirmed that π ′paths which are the same up to a minimal π ′ -deformation in G ′ have the same parity. But γ has parity 1 whereas a one-point path has parity 0. Hence γ is not π ′ -reducible in G ′ , a contradiction. 2

Since every planar pgads is simply connected (Corollary 4.6), a special case of the above proposition is: Corollary 5.2 Every planar gads is orientable.

The Structure of Loops in a GADS

Let G = ((V, π, L), (κ, λ)) be a gads and let L be an arbitrary loop of G. In this section we present some properties that κ ∩ L {2} and λ ∩ L {2} must have. These properties will be used in the next section. We begin with: Lemma 6.1 Let C be a simple closed (κ ∩ λ)-curve in the loop L, and let x and y be distinct vertices of C. Then: Proof: To prove the first assertion of (1), let a and b be (κ∩λ)-adjacent points in C \ {x, y}. We need to show that a and b belong to the same π-component of L \ {x, y}. But if they did not, then x and y would lie in opposite π-cutintervals of L associated with the (κ ∩ λ)-adjacent vertices a and b, and (by Axiom 3) no (κ ∩ λ)-path from x to y in L \ {a, b} would exist. As such a (κ ∩ λ)-path does exist (because x and y belong to C \ {a, b}, which is the set of vertices of a (κ ∩ λ)-path in L), the first assertion of (1) is proved. Now suppose x and y are not (κ ∩ λ)-consecutive on C, and let c and d be the two (κ ∩ λ)-neighbors of x on C. Suppose the second assertion of (1) does not hold. Then the first assertion of (1) implies that c and d both lie in the same π-component of L \ {x, y}. Hence we may assume without loss of generality that c and y lie in opposite π-cut-intervals of L associated with x and d. It then follows from Axiom 3 that (since x and d are (κ ∩ λ)-adjacent) there does not exist a (κ ∩ λ)-path from c to y in L \ {x, d}. But such a (κ ∩ λ)-path exists (as c and y belong to C \ {x, d}, which is the set of vertices of a (κ ∩ λ)-path in L), and this contradiction establishes the second assertion of (1).

(1) Each (κ ∩ λ)-component of C \ {x, y} is contained in a π-component of L \ {x,
Still working under the hypothesis that x and y are not (κ ∩ λ)-consecutive on C, we now prove assertion (2) by showing that L \ {x, y} is κ-(λ-)connected if and only if C \{x, y} is κ-(λ-)connected. The "if" part of this fact follows from the second assertion of (1). To prove the "only if" part, suppose Assertion (3) follows from assertion (2); we leave the details of its proof to the reader. 2

L \ {x, y} is κ-(λ-)connected. We need to show that C \{x, y} is κ-(λ-)connected too. Since L \ {x, y} is κ-(λ-)connected, some a ∈ I L 1 is κ-(λ-)
We now use Lemma 6.1 to prove the following theorem, which is the main result of this section: Theorem 6.2 Let C be a simple closed (κ ∩ λ)-curve in the loop L. Then C has one of the following properties:

(1) For all distinct x, y ∈ C, {x, y} ∈ κ.

(2) For all distinct x, y ∈ C, {x, y} ∈ λ.

Sketch of proof:

If |C| = 3 then the theorem holds, so we may assume |C| > 3. Then it follows from Lemma 6.1(2) that there is a (λ \ κ)-or (κ \ λ)edge in C {2} .

We can show that if x, a, and b are vertices of C then it is impossible that both {x, a} ∈ κ \ λ and {x, b} ∈ λ \ κ. This can be established by induction on the size of the (κ ∩ λ)-cut-interval of C associated with a and b that does not contain x, using Lemma 6.1 [START_REF] Fourey | Intersection number of paths lying on a digital surface and a new Jordan theorem[END_REF][START_REF] Fourey | Intersection number and topology preservation within digital surfaces[END_REF]. (We begin by verifying that {x, a} ∈ κ \ λ and {x, b} ∈ λ \ κ cannot both be true if a and b are (κ ∩ λ)-consecutive on C; otherwise we could deduce a contradiction to Lemma 6.1(2,3).)

Next, we argue that if {x, a} is a (κ\λ)-edge in C {2} , and y and z are the (κ∩λ)neighbors of x on C, then {y, z} is a κ-edge. For otherwise Lemma 6.1(2) would imply that there is some vertex b, in the (κ ∩ λ)-cut-interval of C associated with y and z that does not contain x, such that {x, b} is a λ-edge (and hence a (λ \ κ)-edge), and this would contradict the result of the previous paragraph.

Thus if x is a vertex of a (κ\λ)-edge in C {2} , then each of the (κ∩λ)-neighbors of x on C is also a vertex of a (κ \ λ)-edge in C {2} . If follows that if there is a (κ\λ)-edge in C {2} , then every vertex of C is a vertex of a (κ\λ)-edge in C {2} . This would imply that no vertex of C is a vertex of a (λ \ κ)-edge in C {2} , so that there are no (λ \ κ)-edges in C {2} , whence (by Lemma 6.1(2)) every pair of vertices of C are κ-adjacent. Symmetrically, if there is a (λ \ κ)-edge in C {2} then all pairs of vertices of C are λ-adjacent. 2

We will use the term (κ ∩ λ)-subloop (of G) to mean a simple closed (κ ∩ λ)curve that is contained in a loop of G. Figure 3 shows a loop that can be subdivided into three (κ ∩ λ)-subloops. Remark 6.3 It is not hard to deduce from Axiom 3 that if two vertices of a loop of G are π-, (κ \ λ)-, or (λ \ κ)-adjacent, then there is a unique (κ ∩ λ)subloop that is contained in the loop and contains both vertices. Moreover, if two vertices of a loop of G are (κ ∩ λ \ π)-adjacent, then there are just two (κ ∩ λ)-subloops that are contained in the loop and contain both vertices. One can further show (using Lemma 6.1(2)) that if S is the set of all (κ ∩ λ)subloops of the gads G = ((V, π, L), (κ, λ)), then ((V, κ ∩ λ, S), (κ, λ)) is also a gads.

From the first sentence of Remark 6. The reader can verify that Theorem 6.2, the assertions of Remark 6.3, and Lemma 6.4 are all consistent with Figure 3. The final result of this section says that Lemma 6.1(1) is also true if C is a simple closed κ-or λ-curve rather than a simple closed (κ ∩ λ)-curve. This result implies that, for ρ = κ, λ, or (κ ∩ λ), a ρ-parameterization of a simple closed ρ-curve in the loop L must be a subsequence of a π-parameterization of L -loosely speaking, it must proceed in a single direction around L, and cannot reverse direction at some vertex.

• L ρ ρ (κ ∩ λ) = ρ ∩ ρ

The Intersection Number

Let G = ((V, π, L), (κ, λ)) be an orientable gads and let Ω be a coherent orientation of G. In this section we define an intersection number of a (κ ∪ λ)path p with a closed (κ∪λ)-path c. This number is denoted by I Ω c,p . It is defined only if every common vertex of the two paths is a nonsingular interior vertex of G. Loosely speaking, it is the number of times the path p crosses from the right of the closed path c to its left, minus the number of times p crosses c from left to right.

Our intersection number is a generalization to gads of the intersection number between paths of surfels in digital boundaries that was defined and used in [START_REF] Fourey | Intersection number of paths lying on a digital surface and a new Jordan theorem[END_REF], except that we only define the intersection number when one of the two paths is closed. 13 Our main result about the intersection number (Theorem 7.7) is that in an orientable gads the intersection number of a λ-path with a closed κ-path is invariant under λ-homotopic deformations of the λ-path, assuming that all vertices of the closed κ-path are nonsingular interior vertices of G. As we shall see in the next section, this fact can be used to prove our Jordan curve theorem for planar gads (Theorem 4.8 above).

The definition of the intersection number is based on the idea that, for each three-vertex segment (x 0 , x 1 , x 2 ) of a (κ ∪ λ)-path in which x 1 is a nonsingular interior vertex of G, we can partition the set N * L (x 1 ) \ {x 0 , x 2 } into a "left" side and a "right" side with respect to the segment (x 0 , x 1 , x 2 ), using the πcycle N * Ω,x 0 (x 1 ) defined in Section 5.2. The details of this are given in the next definition. Note that since {x 0 , x 1 }, {x 1 , x 2 } ∈ κ ∪ λ, Axiom 2 implies that x 0 , x 2 ∈ N * L (x 1 ), so that x 2 lies on the π-cycle N * Ω,x 0 (x 1 ). Definition 7.1 Let (x 0 , x 1 , x 2 ) be a segment of a (κ ∪ λ)-path, where x 1 is a nonsingular interior vertex of G, and let N * Ω,x 0 (x 1 ) = (v 0 , . . . , v n ), so that

v 0 = v n = x 0 . Let h ∈ {0, . . . , n} be the integer such that v h = x 2 . Then we define R Ω (x 0 , x 1 , x 2 ) = {v i | 0 < i < h} and L Ω (x 0 , x 1 , x 2 ) = {v i | h < i < n}. Let c = (x 0 , . . . , x l ) be a closed (κ∪ λ)-path (so that x 0 = x l ). If x i is a nonsin- gular interior vertex of G, we write Right c Ω (i) for R Ω (x (i-1) mod l , x i , x (i+1) mod l ) and Left c Ω (i) for L Ω (x (i-1) mod l , x i , x (i+1) mod l ). Thus if x i is a nonsingular inte- rior vertex of G then Left c Ω (i) ∪ Right c Ω (i) = N * L (x i ) \ {x (i-1) mod l , x (i+1) mod l }.

Note that the functions Left c

Ω and Right c Ω are determined by the function Ω and the sequence c; they do not depend on G (except in that G must be a gads whose loops constitute the domain of Ω). Now let {y, z} be a (κ ∪ λ)-edge. If one of y and z is not an interior vertex of G or is a singularity of G, and that vertex is also a vertex of c, then W c (y,z) is undefined. Otherwise, we define

W c (y,z) = ∑ l-1 i=0 W c (y,z) (i), where: (1) W c (y,z) (i) = -0.5 if y = x i and z ∈ Right c Ω (i), or if z = x i and y ∈ Left c Ω (i).
13 It is quite easy to extend our definition to two paths that are not closed.

(2) W c (y,z) (i) = +0.5 if y = x i and z ∈ Left c Ω (i), or if z = x i and y ∈ Right c Ω (i). (3) W c (y,z) (i) = 0 otherwise. Definition 7.2 (intersection number) Let p = (y 0 , . . . , y h ) be a (κ ∪ λ)path and c a closed (κ ∪ λ)-path, such that every common vertex of c and p is a nonsingular interior vertex of G. Then the intersection number of p with c, denoted by I Ω c,p , is defined to be

∑ h-1 i=0 W c (y i ,y i+1
) . The next two lemmas state fundamental properties of the intersection number that follow without much difficulty from this definition.

each i such that x i is a nonsingular interior vertex of G, (a) N * κ (x i ) \ C ⊆ Right c Ω (i), and (b) C \ {x (i-1) mod l , x i , x (i+1) mod l } ⊆ Left c Ω (i). (2) For each i such that x i is a nonsingular interior vertex of G, (a) N * κ (x i ) \ C ⊆ Left c Ω (i)
, and (b) C \ {x (i-1) mod l , x i , x (i+1) mod l } ⊆ Right c Ω (i). Proof: It follows from Lemma 6.5 that there is a π-parameterization c ′ of L that begins and ends at x 0 = x l and which contains c as a subsequence. The π-cycle c ′ must be equivalent to Ω(L) or to Ω(L) -1 . We now assume c ′ is equivalent to Ω(L) and deduce that property (1) holds. (In the other case it follows from a symmetrical argument that (2) holds.) Let x i ∈ C be a nonsingular interior vertex of G. From its very definition, it is readily seen that the set Left c Ω (i) is the π-cut-interval of L associated with x (i-1) mod l and x (i+1) mod l that does not contain x i . Let I denote that π-cut-interval.

On applying Lemma 6.5 with (x, y) = (x (i-1) mod l , x (i+1) mod l ), we deduce that C \ {x (i-1) mod l , x i , x (i+1) mod l } ⊆ I = Left c Ω (i), and so (b) holds. Regarding (a), note that (since Left c Ω (i) = I) we have

N * κ (x i ) \ C = N * κ (x i ) ∩ (Left c Ω (i) ∪ Right c Ω (i)) \ C ⊆ (N * κ (x i ) ∩ I \ C) ∪ Right c Ω (i).
It follows that, to prove (a), it is enough to verify that N * κ (x i ) ∩ I \ C = ∅. If |C| = 3, then l = 3 and x (i-1) mod l is λ-adjacent to x (i+1) mod l . In this case Axiom 3 implies that N * κ (x i ) ∩ I = ∅, as required. Now suppose |C| > 3. Then

A Proof of the Jordan Curve Theorem

We now outline a proof of the Jordan curve theorem for planar gads (Theorem 4.8 above). Since a planar pgads is orientable (Corollary 5.2), has no singularities (Proposition 4.7), and is simply connected (Corollary 4.6), this theorem follows from the following more general result:

Theorem 8.1 Let G = ((V, π, L), (κ, λ)) be a gads that is a subGADS of an orientable pgads G ′ = ((V ′ , π ′ , L ′ ), (κ ′ , λ ′ )) which has no singularities. Let c be a κ-parameterization of a simple closed κ-curve C of G such that:

(1) C is not included in any loop of G.

(2) Every vertex in C is an interior vertex of G.

(

3) c is κ ′ -reducible in G ′ .
Then V \ C has exactly two λ-components, and, for each vertex

x ∈ C, N * λ (x) intersects both λ-components of V \ C.
It is perhaps worth mentioning that in this theorem the hypothesis that G ′ is orientable is not really necessary, but is included because we wish to give a proof of the theorem that uses the intersection number (which is only defined in orientable gads).

Regarding condition (2), note that an interior vertex v of G cannot be a vertex of a (π ′ \π)-edge, cannot lie on a loop of G ′ in L ′ \L, and cannot be a singularity of G, for in all of these cases v would be a singularity of G ′ , contrary to the hypothesis that G ′ has no singularities.

As a first step in proving Theorem 8.1, we establish the following: Lemma 8.2 Let G = ((V, π, L), (κ, λ)) be a gads. Let x be a nonsingular interior vertex of G, let Ω x be a coherent local orientation of G at x, let y ∈ N * L (x), and let S be the set of vertices of a contiguous subsequence s of N * Ωx,y (x) such that S ∩ N * κ∪λ (x) is nonempty. Suppose further that no vertex in s is (κ ∩ λ)-adjacent to x, with the possible exceptions of the first and last vertices of s. Then there is a (κ ∩ λ)-subloop G in a loop of G such that: [START_REF] Alexandrov | Combinatorial topology[END_REF] x ∈ G, and (2) S ∩ N * κ∪λ (x) is the set of vertices of a contiguous subsequence of a (κ ∩ λ)parameterization of G.

Proof: Since no vertex in s (except possibly the first or last vertex) is (κ∩λ)adjacent to x, it follows from the definition of N * Ωx,y (x) that S is contained in some loop L of G that contains x. Moreover, there is a π-parameterization g of L that begins and ends at x and contains s as a contiguous subsequence. Let x -and x + be respectively the first and the last vertex in the sequence g that lies in S ∩ N * κ∪λ (x). Let g -be a shortest subsequence of g that is a (κ ∩ λ)-path from x + to x. Let g 0 be a shortest subsequence of g that is a (κ ∩ λ)-path from x -to x + . Let g + be a shortest subsequence of g that is a if A is either empty or a singleton set, or if A is a finite ρ-connected set with the following property: there are two (and only two) elements of A that each have just one ρ-neighbor in A, and all other elements of A have exactly two ρ-neighbors in A. Note that if C is any simple closed ρ-curve and p ∈ C then C -{p} is a ρ-arc. Each element of a ρ-arc A that does not have two ρ-neighbors in A is called an extremity of A. Proposition 8.5 Let G = ((V, π, L), (κ, λ)) be a gads. Let A be a κ-arc such that every vertex in A is a nonsingular interior vertex of G. Then V \ A is λ-connected.

Proof: We first assert that if x is an extremity of A, then N * κ∪λ (x) \ A is λ-connected. Indeed, let x be an extremity of A (so that x is a nonsingular interior vertex of G), and let Ω x be a coherent local orientation of G at x. Let y be the κ-neighbor of x in A, unless |A| = 1 in which case let y be any κ-neighbor of x. Let s = (z 0 , . . . , z h ) be a subsequence of the π-cycle N * Ωx,y (x) such that s consists of all the elements of N * κ∪λ (x). Let (m 0 , . . . , m p ) be the strictly increasing sequence of integers such that {z m 0 , . . . , z mp } = N * κ∪λ (x)\A. We can now prove the assertion by showing that {z m k , z m k+1 } ∈ λ for all k (0 ≤ k < p), using arguments that are very similar to arguments used in the corresponding part of the proof of Lemma 8.3.

The proposition can be deduced from the assertion by induction on |A|. If |A| = 0, the result follows from the π-connectedness of V . Assume the result holds when |A| = k, and suppose |A| = k + 1. Let x be an extremity of A, and let A ′ = A \ {x}. Let v be any vertex in V \ A. By the induction hypothesis v is λ-connected in V \ A ′ to x, and hence to some vertex of N * λ (x) \ A ′ . A shortest λ-path in V \ A ′ from v to N * λ (x) \ A ′ does not pass through x. Hence v is λ-connected even in V \ A to some vertex of N * λ (x) \ A ′ ⊆ N * κ∪λ (x) \ A. Since v is an arbitrary vertex in V \ A and N * κ∪λ (x) \ A is λ-connected, V \ A is λ-connected. 2 Proof of Theorem 8.1: From Proposition 8.4 we know that V \ C has at least two λ-components. Now let x be a vertex of C, and let A be the κ-arc C \ {x}. Let v be any vertex in V \ C. By Proposition 8.5, v is λ-connected in V \ A to x, and hence to some vertex in N * λ (x) \ A. A shortest λ-path in V \ A from v to N * λ (x) \ A does not pass through x, so v is λ-connected even in V \ C to some vertex in N * λ (x) \ A. Since this applies to any vertex v in V \ C, every λ-component of V \ C intersects N * λ (x) \ A. Moreover, since N * λ (x) \ A ⊆ N * κ∪λ (x) \ C, we can deduce that V \ C has no more λ-components than N * κ∪λ (x) \ C. But if c = (x 0 , . . . , x l ), so that x l = x 0 , and i is the integer in {0, . . . , l -1} such that x = x i , then N * κ∪λ (x) \ C = N * κ∪λ (x)∩(Left c Ω (i)∪Right c Ω (i))\C does not have more than two λ-components, by Lemma 8.3. Hence V \ C cannot have more than two λ-components. 2

Concluding Remarks

This paper presents a new, axiomatic, approach to 2D digital topologyincluding the digital topology of boundary surfaces -in which the objects of study are mathematical structures we call gads. A gads is a surface complex equipped with a pair of adjacency relations (on the vertices of the complex) that satisfy three axioms. Instances of this general concept include digital spaces (on planar or on boundary surface grids) based on each of the good pairs of adjacency relations that have previously been used by ourselves and others in 2D digital topology. Some results that have been established in the literature for certain specific digital spaces have been generalized to gads (e.g., a homotopy invariance theorem for intersection numbers of digital paths, and a digital Jordan curve theorem). There are many other results of digital topology for which this could be done, such as results about simple points and boundary tracking. The problem of developing a 3D version of this theory seems more challenging.

  y) denotes the Euclidean distance between x and y.Example 2.11 A "torus-like" finite pgads

Definition 3 .

 3 2 (ρ-homotopic paths) Two ρ-paths c and c ′ in X with the same initial and the same final vertices are ρ-homotopic within X in G if there exists a sequence of ρ-paths c 0 , . . . , c n in X such that c 0 = c, c n = c ′ and, for 0 ≤ i ≤ n -1, c i and c i+1 are the same up to an elementary G-deformation. Two ρ-paths with the same initial and the same final vertices are said to be ρ-homotopic in G if they are ρ-homotopic within V in G. Each equivalence class of this equivalence relation is called a ρ-homotopy class of ρ-paths in G.

Definition 4 . 1 (

 41 Euler characteristic of a GADS) Let G = ((V, π, L), (κ, λ)) be a finite gads. Then the integer |V | -|π| + |L| is called the Euler characteristic of G, and is denoted by χ(G).

Theorem 4 . 8 (

 48 Jordan curve theorem) Let PG = ((

Fig. 1 .

 1 Fig. 1. (a) The set of loops which contain a vertex x, and a coherent local orientation Ω x of G at x. (b) The corresponding π-cycle N * Ωx,y (x).

Fig. 2 .

 2 Fig. 2. Illustration of Lemma 6.1(3).

  adjacent to some b ∈ I L 2 , where I L 1 and I L 2 are the two π-components of L \ {x, y}. Now x and y lie in opposite π-cut-intervals of L associated with the κ-(λ-)adjacent vertices a and b. Hence (by Axiom 3) every (κ ∩ λ)-path in L from x to y passes through a or b. As there are two simple (κ ∩ λ)-paths in C from x to y, and these paths have no common vertex other than x and y, one of these paths passes through a and the other passes through b. Hence a and b lie in C. As a and b lie in opposite π-components of L \ {x, y}, they lie in opposite (κ ∩ λ)-components of C \ {x, y} (by the first assertion of (1)). So (since a is κ-(λ-)adjacent to b) C \ {x, y} is κ-(λ-)connected, as required.

3 ,Lemma 6 . 4

 364 Axiom 3, and Theorem 6.2, one can deduce the following: Let (ρ, ρ) = (κ, λ) or (λ, κ), and let C be any simple closed ρcurve in the loop L such that |C| ̸ = 3. Then C is a (κ ∩ λ)-subloop. Moreover, {x, y} ∈ ρ for all x, y ∈ C.

Fig. 3 .

 3 Fig.3. Illustration of Theorem 6.2, Remark 6.3, and Lemma 6.4. This is a possible loop in a gads, if the eight (κ ∩ λ)-edges that belong to just one of the three (κ ∩ λ)-subloops are proto-edges and the other two (κ ∩ λ)-edges are not.

Lemma 6 . 5

 65 Let ρ = κ, λ, or (κ ∩ λ), and let C be any simple closed ρ-curve in the loop L. Then, for all distinct x, y ∈ C, each ρ-component of C \ {x, y} is contained in a π-component of L \ {x, y}. Moreover, if x and y are distinct vertices of C that are not ρ-consecutive on C, then the two ρ-components of C \ {x, y} lie in opposite π-components of L \ {x, y}. Proof: If |C| = 3 the result is trivial. If |C| > 3 then the result follows from Lemma 6.1(1) and Lemma 6.4, because the latter implies that C is a (κ ∩ λ)subloop, and that two vertices of C are ρ-consecutive on C if and only if they are (κ ∩ λ)-consecutive on C. 2

Lemma 7 . 3 2 . 7 . 4

 73274 Let c be a closed (κ ∪ λ)-path, and let p ′ , p 1 and p 2 be (κ ∪ λ)paths such that p ′ = p 1 .p 2 . Suppose further that every common vertex of c and p ′ is a nonsingular interior vertex of G.Then I Ω c,p ′ = I Ω c,p 1 + I Ω c,p Lemma If c 1 and c 2 are closed (κ ∪ λ)-paths and every common vertex of c 1 and c 2 is a nonsingular interior vertex of G, then I Ω c 1 ,c 2 = -I Ω c 2 ,c 1 .We will need two more lemmas to prove the main result of this section. Lemma 7.5 Let C be a simple closed λ-curve whose vertices all lie in a single loop L of G. Let c = (x 0 , . . . , x l ) be a λ-parameterization of C. (Here x l = x 0 .) Then C has one of the following two properties: (1) For

If α is an irreflexive symmetric binary relation on the set G of all points of a 2D or 3D Cartesian or non-Cartesian grid, then α is referred to as the k-adjacency relation on G, and is denoted by the positive integer k, if for all p ∈ G the set {q ∈ G | p α q} contains just k points and they are all strictly closer to p (in Euclidean distance) than is any other point of G \ {p}.

ρ can be viewed as a binary, symmetric, and irreflexive relation on P , and (P, ρ) as an undirected simple graph.

Thus x M y will mean that the pair (x, y) belongs to the relation denoted by M .

E.g., if p, q ∈ Z 2 are 8-adjacent but not 4-adjacent, then N * 8 (p) \ {q} is 4-simply connected but not 8-simply connected in the gads ((Z 2 , 4, L 2×2 ),[START_REF] Kong | On topology preservation in 2D and 3D thinning[END_REF][START_REF] Herman | Oriented surfaces in digital spaces[END_REF]).

Acknowledgments

The authors are grateful to the referees for their comments on the manuscript and their helpful suggestions for improving it.

Supported by U.S. NIH grant HL-740472.

 Lemma 6.4implies that C is a (κ ∩ λ)-subloop, and it is readily seen from Axiom 3 that a vertex in I which does not belong to C cannot be κ-adjacent to x i . Hence N * κ (x i ) ∩ I \ C = ∅, as required. 2

Lemma 7. [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] Let c be a λ-parameterization of a simple closed λ-curve that lies in a single loop of G, and let c ′ be a closed κ-path such that every common vertex of c and c ′ is a nonsingular interior vertex of G. Then I Ω c,c ′ = 0. Proof: Let c = (x 0 , . . . , x l ), let C be the simple closed λ-curve parameterized by c, and let c ′ = (y 0 , . . . , y h ). (Thus x l = x 0 and y h = y 0 .) For all j such that y j and y j+1 both lie on C, W c (y j ,y j+1 ) = 0. (It is plain that W c (y j ,y j+1 ) (i) = 0 except possibly at the two values of i in 0, . . . , l -1 for which x i ∈ {y j , y j+1 }, and that W c (y j ,y j+1 ) (i) = 0 for both of those values of i if y j and y j+1 are λconsecutive vertices of C. Moreover, W c (y j ,y j+1 ) (i) is +0.5 for one value of i and -0.5 for the other if y j and y j+1 are not λ-consecutive on C, since the (b) part of ( 1) or (2) in Lemma 7.5 applies at both of y j and y j+1 .) Also, W c (y j ,y j+1 ) has one nonzero value (±0.5) for all j such that y j ∈ C and y j+1 / ∈ C, and has the opposite nonzero value for all j such that y j / ∈ C and y j+1 ∈ C, since the (a) part of (1) or (2) in Lemma 7.5 applies in all such cases at the one of y j and y j+1 that lies on C. As c ′ is a closed κ-path, there are exactly as many values of j in 0, . . . , h -1 for which y j ∈ C and y j+1 / ∈ C as there are values of j for which y j / ∈ C and y j+1 ∈ C.

Using this lemma and Proposition 3.4, we now prove the main result of this section. Note that (by Property 2.4) this theorem, Lemma 7.5, and Lemma 7.6 all remain true when κ is replaced by λ and λ by κ.

Theorem 7.7 Let G = ((V, π, L), (κ, λ)) be an orientable gads, and let Ω be a coherent orientation of G. Let c be a closed κ-path all of whose vertices are nonsingular interior vertices of G, and let p and q be two λ-paths which are λ-homotopic in G. Then I Ω c,p = I Ω c,q . Corollary 7.8 Under the hypotheses of Theorem 7.7,

Proof of Theorem 7.7: By Proposition 3.4, it is sufficient to prove Theorem 7.7 when p and q are the same up to a minimal λ-deformation in G. There are two cases. First suppose p = p 1 .(x, y, x).p 2 and q = p 1 .p 2 , where {x, y} ∈ λ. Then (by Lemma 7.3)

γ,c = 0 and so, by Lemma 7.4,

Suppose there is a vertex v in S∩N * κ∪λ (x)\G 0 . Then, in the π-parameterization g of L, the vertex v lies somewhere between two (κ ∩ λ)-adjacent vertices in G 0 . On applying Axiom 3 to those two vertices, we deduce that v ̸ ∈ N * κ∪λ (x), a contradiction. Hence S ∩ N * κ∪λ (x) ⊆ G 0 . By Theorem 6.2, the (κ∩λ

, and therefore G satisfies (2). 2 Lemma 8.3 Under the hypotheses of Theorem 8.1, let Ω be a coherent orientation of G ′ , and let c = (x 0 , . . . , x l ), so that x l = x 0 . Then, for all i ∈ {0, . . . , l}, each of the sets Left c

Proof: Write i⊕1 and i⊖1 for ((i+1) mod l) and ((i-1) mod l), respectively. Let R = Right c Ω (i) ∩ N * κ∪λ (x i ). Claim 1: There is a vertex in R \ C that is λ-adjacent to x i . This is true if there is a vertex v in Right c Ω (i) that is (κ ∩ λ)-adjacent to x i , as such a vertex v cannot belong to C (for otherwise C would not be a simple closed κ-curve). Now suppose there is no such v. Then, on applying Lemma 8.2 with S = Right c Ω (i) ∪ {x i⊖1 , x i⊕1 } and x = x i , we deduce that there is a

The vertices x i⊖1 and x i⊕1 of G are not κ-adjacent. Otherwise {x i⊖1 , x i , x i⊕1 } would be a simple closed κ-curve, so that C = {x i⊖1 , x i , x i⊕1 } ⊆ L (by Property 2.1) contrary to condition (1) of Theorem 8.1. Hence it follows from Theorem 6.2 that all pairs of distinct vertices in G are λ-adjacent, and so all vertices in R ∪ {x i⊖1 , x i⊕1 } are λ-adjacent to x i . To establish Claim 1, it remains only to show that R ̸ ⊆ C. Since x i is (κ ∩ λ)-adjacent to x i⊖1 and to x i⊕1 , and since R ∪ {x i⊖1 , x i⊕1 } is a contiguous subsequence of a (κ ∩ λ)-parameterization of the simple closed (κ∩λ)-curve G that contains x i , we must have Let s = (z 0 , . . . , z h ) be the subsequence of the π-cycle N * Ω,x i⊖1 (x i ) consisting of the vertices in R. Let (m 0 , . . . , m p ) be the strictly increasing sequence of integers such that {z m 0 , . . . , z mp } = R \ C. We now prove that {z m 0 , . . . , z mp } is λ-connected by showing that {z m k , z m k+1 } ∈ λ for all k (0 ≤ k < p). Indeed, no vertex z j such that m k < j < m k+1 can be (κ ∩ λ)-adjacent to x i (since all vertices z j such that m k < j < m k+1 belong to C, and x i⊖1 and x i⊕1 are the only κ-neighbors of x i on C). On applying Lemma 8.2 to the contiguous subsequence of N * Ω,x i⊖1 (x i ) whose first and last vertices are z m k and z m k+1 , we deduce that x i , z m k , and z m k+1 all belong to a (κ ∩ λ)-subloop H in a loop. By Theorem 6.2, one of the following is true:

(1) All pairs of distinct vertices of H are λ-adjacent.

(2) All pairs of distinct vertices of H are κ-adjacent.

In case 1, {z m k , z m k+1 } ∈ λ. In case 2, z m k and z m k+1 must be (κ∩λ)-consecutive on H. (For otherwise there would be a vertex z * on H that lies between them in N * Ω,x i⊖1 (x i ), by Lemma 6.1 [START_REF] Alexandrov | Combinatorial topology[END_REF]. Since 2)], we have z * ∈ R. Therefore z * = z j for some j such that m k < j < m k+1 . But z j = z * / ∈ C since x i⊖1 and x i⊕1 are the only κ-neighbors of x i on the simple closed κcurve C, and so z j ∈ R \ C. This contradicts the definition of the sequence (m 0 , . . . , m p ).) Thus in both cases {z m k , z m k+1 } ∈ λ, as required. This proves Claim 2.

Thus Right

Let Ω be a coherent orientation of G ′ , let c = (x 0 , . . . , x l ) (so that x l = x 0 ), and pick i ∈ {0, . . . , l}. By Lemma 8.3 there exist vertices y ∈ Left c Ω (i) ∩ N * λ (x i ) \ C and z ∈ Right c Ω (i) ∩ N * λ (x i ) \ C. As V \ C is λ-connected, there is a λ-path α in V \ C from y to z. Note that α is also a λ ′ -path of G ′ , since λ ⊆ λ ′ (by Property 2.6). The closed λ ′ -path α ′ = α.(z, x i , y) satisfies I Ω c,α ′ = 1. But since all vertices of a pgads are interior vertices and c is κ ′ -reducible in the pgads G ′ (which has no singularities), it follows from Corollary 7.8 that I Ω α ′ ,c = 0, so that (by Lemma 7.4) I Ω c,α ′ = 0, a contradiction. 2

The next proposition will be used to prove that the set V \ C in Theorem 8.1 cannot have more than two λ-components. For any set ρ of unordered pairs of vertices of a gads, we say that a set A of vertices of the gads is a ρ-arc