Covering with Excess One: Seeing the Topology
Han Wang
Abstract
We have initiated the study of topology of the space of coverings on grid
domains. The space has the following constraint: while all the covering agents
can move freely (we allow overlapping) on the domain, their union must cover
the whole domain. A minimal number N of the covering agents is required
for a successful covering of the domain. In this paper, we demonstrate beau-
tiful topological structures of this space on grid domains in 2D with N + 1
coverings, the topology of the space has the homotopy type of 1 dimensional
complex, regardless of the domain shape. We also present the Euler character-
istic formula which connects the topology of the space with that of the domain
itself.
1
INTRODUCTION
1.1
BACKGROUND
The spaces of coverings appear in many applications. Usually a (finite) family of
balls are placed randomly to cover a metric space; such stochastic covering known
as a coverage process has been studied extensively (see e.g., [4]). In recent years,
coverage problem in the context of sensor networks and robot motion planning
has become an active research area; robot swarms (sensors) are deployed to cover
a given domain (see [2], [6], etc.). If we consider each moving robot to be a labelled
covering agent, we can formulate the space of coverings as follows:
Definition 1.1. The covering configuration space of n labelled points on a topological
space X is defined as the space
CovX(n, F) := {(f1, f2, . . . , fn), fi ∈F :
n[
i=1
Mfi = X},
where F is a topological space parametrizing subsets of X as {Mf}f∈F.
Recently using topological approach to study the covering configuration space,
among other applied configuration spaces (e.g., configuration space of hard spheres [1])
starts to bring new insights into the subject. Understanding its topological features
1
arXiv:1312.7477v1  [math.GN]  28 Dec 2013
can be useful in many applications. The total Betti number of this space, for ex-
ample, would provide lower bounds for the depth of the algebraic decision trees
(which are used to decide membership in a semialgebraic set in theoretical com-
puter science), according to Yao-Lov´asz-Bj¨orner [7].
As our first attempt to understanding the covering configuration space for pla-
nar and higher dimensional domains, in the sequel we shall focus on grid domains
which are formed by square plaques in 2D, all the coverings are of the same shape
as cubical, in order to cope with the domain geometry in a nice fashion. By our as-
sumption, there are N + 1 such covering agents, and the domain can be covered by
exactly N of them. For simplicity whenever possible, we shall denote this covering
configuration space as CovGN (N + 1), where GN denotes the grid domain that can
be covered precisely by N unit square plaques.
1.2
SIMPLE EXAMPLES
The 1D scenario is simple: for a line segment (say, unit closed interval), consider
covering it with n balls of the same length. Y. Baryshnikov first studied this case,
it turns out that the covering configuration space is homotopy equivalent to the
skeleton of the permutahedron [8] with n vertices. More precisely, denote CovI(n, r)
as the covering configuration space for unit interval I with n balls of radii r, we
have
Theorem 1.2 (Y. Baryshnikov).
CovI(n, r) ≃h Skelk(Πn−1),
where Πn−1 is the permutahedron with each vertice coresponding to a permutation of
(1, . . . , n), k = n −⌈1
2r⌉and ⌈1
2r⌉is the minimal number of r-balls to cover [0, 1]. k
is the excess number.
Based on the theorem, we have the conclusion that for covering I with excess
one, we have
CovIN (N + 1) ≃h Skel1(ΠN).
For illustration purpose of Theorem 1.2, consider the following simplest non-
trivial example: covering I with three points. The reader may find this helpful for
intuition.
As r varies, CovI(3, r) changes. The trivial case happens when r is sufficently
large, say, r = 1
2, then CovI(3, r) is contractible to a point. On the other extreme
case, when r is too small, CovI(3, r) would be ∅, which means that there is no place-
ment available to cover I. Suppose r = 1
6, then we have to place the three balls side
by side without any overlap. If unlabeled, this corresponds to one point in the
covering configuration space. Therefore, CovI(3, 1
6) consists of 6 isolated points.
Suppose r = 1
4, we are able to cover I with exactly 2 points, the third one can move
2
freely on I, acting as the excess covering agent. When it overlaps with one or the
other point (we shall call such placement as a critical configuration), the before-
fixed one is free of being restricted in moving, and can move anywhere on I, as
now it acts as the excess covering. Performing such permutation successively will
lead to a rotation, hence CovI(3, 1
4) is homotopy equivalent to a hexagon, or simply
a circle. This is exactly what Theorem 1.2 tells us. On the other hand once iso-
lated points become connected in the configuration space, as the number of excess
covering agents increases from 0 to 1.
[1
2, 3]
[1, 3
2]
[3
1, 2]
[3, 2
1]
[2
1, 3]
[1, 2
3]
123
132
312
321
231
213
1
2
3
3
1
2
Figure 1: Visualization of the covering configuration space for 3 points to cover I
while 2 is enough. The figure shows how the 1 skeleton of permutahedron Π2 can
be thought of as a homotopy equivalence of a hexagon with vertices labelled by
critical configurations, plus 6 triangular cells glued on its edges.
Here we have another point to make, which is a little technical but turns out
to be very helpful in the proof we will present later: there is a one-to-one corre-
spondence between an edge in Skel1(Π2) and a critical configuration point. The
visualization is given in figure 1. The inner hexagon has its vertices labelled by
those critical configurations. Edge is formed when we move the excess agent to
form another critical configuration. Skel1(Π2) (the bigger hexagon) can be recov-
ered first by the expansion of the inner hexagon and then by deformation retracting
to it. We shall make use of this ‘dual’ viewpoint as it helps us identify the critical
configurations while the skeleton of a permutahedron would not naturally do so.
As a more interesting example, the visualization of CovI3(4) is given in figure 2.
Now consider a 2D grid domain G2×2 formed by 2 by 2 square plaques. The
excess agent have the freedom of moving either vertically or horizontally, with
other four covering agents fixed. Its free patrolling region Q is shown in figure 3.
Note that restricting the excess’s move on one edge of ∂Q becomes the problem
of covering 1D line segments, we know CovI(3, 1/2) has the homotopy type of a
hexagon, moving on one edge of ∂Q traverses one edge of the hexagon, so ∂Q can
be glued with Skel1(Π2) along that edge. Let’s identify Q with a 2 by 2 labeling
matrix C, namely, if cij ∈{1, 2, 3, 4, 5} for all i, j = 1, 2, then C is identified with Q;
3
Covering with Excess One: Seeing the Topology
Han Wang
Abstract
We have initiated the study of topology of the space of coverings on grid
domains. The space has the following constraint: while all the covering agents
can move freely (we allow overlapping) on the domain, their union must cover
the whole domain. A minimal number N of the covering agents is required
for a successful covering of the domain. In this paper, we demonstrate beau-
tiful topological structures of this space on grid domains in 2D with N + 1
coverings, the topology of the space has the homotopy type of 1 dimensional
complex, regardless of the domain shape. We also present the Euler character-
istic formula which connects the topology of the space with that of the domain
itself.
1
INTRODUCTION
1.1
BACKGROUND
The spaces of coverings appear in many applications. Usually a (finite) family of
balls are placed randomly to cover a metric space; such stochastic covering known
as a coverage process has been studied extensively (see e.g., [4]). In recent years,
coverage problem in the context of sensor networks and robot motion planning
has become an active research area; robot swarms (sensors) are deployed to cover
a given domain (see [2], [6], etc.). If we consider each moving robot to be a labelled
covering agent, we can formulate the space of coverings as follows:
Definition 1.1. The covering configuration space of n labelled points on a topological
space X is defined as the space
CovX(n, F) := {(f1, f2, . . . , fn), fi ∈F :
n[
i=1
Mfi = X},
where F is a topological space parametrizing subsets of X as {Mf}f∈F.
Recently using topological approach to study the covering configuration space,
among other applied configuration spaces (e.g., configuration space of hard spheres [1])
starts to bring new insights into the subject. Understanding its topological features
1
arXiv:1312.7477v1  [math.GN]  28 Dec 2013
can be useful in many applications. The total Betti number of this space, for ex-
ample, would provide lower bounds for the depth of the algebraic decision trees
(which are used to decide membership in a semialgebraic set in theoretical com-
puter science), according to Yao-Lov´asz-Bj¨orner [7].
As our first attempt to understanding the covering configuration space for pla-
nar and higher dimensional domains, in the sequel we shall focus on grid domains
which are formed by square plaques in 2D, all the coverings are of the same shape
as cubical, in order to cope with the domain geometry in a nice fashion. By our as-
sumption, there are N + 1 such covering agents, and the domain can be covered by
exactly N of them. For simplicity whenever possible, we shall denote this covering
configuration space as CovGN (N + 1), where GN denotes the grid domain that can
be covered precisely by N unit square plaques.
1.2
SIMPLE EXAMPLES
The 1D scenario is simple: for a line segment (say, unit closed interval), consider
covering it with n balls of the same length. Y. Baryshnikov first studied this case,
it turns out that the covering configuration space is homotopy equivalent to the
skeleton of the permutahedron [8] with n vertices. More precisely, denote CovI(n, r)
as the covering configuration space for unit interval I with n balls of radii r, we
have
Theorem 1.2 (Y. Baryshnikov).
CovI(n, r) ≃h Skelk(Πn−1),
where Πn−1 is the permutahedron with each vertice coresponding to a permutation of
(1, . . . , n), k = n −⌈1
2r⌉and ⌈1
2r⌉is the minimal number of r-balls to cover [0, 1]. k
is the excess number.
Based on the theorem, we have the conclusion that for covering I with excess
one, we have
CovIN (N + 1) ≃h Skel1(ΠN).
For illustration purpose of Theorem 1.2, consider the following simplest non-
trivial example: covering I with three points. The reader may find this helpful for
intuition.
As r varies, CovI(3, r) changes. The trivial case happens when r is sufficently
large, say, r = 1
2, then CovI(3, r) is contractible to a point. On the other extreme
case, when r is too small, CovI(3, r) would be ∅, which means that there is no place-
ment available to cover I. Suppose r = 1
6, then we have to place the three balls side
by side without any overlap. If unlabeled, this corresponds to one point in the
covering configuration space. Therefore, CovI(3, 1
6) consists of 6 isolated points.
Suppose r = 1
4, we are able to cover I with exactly 2 points, the third one can move
2
freely on I, acting as the excess covering agent. When it overlaps with one or the
other point (we shall call such placement as a critical configuration), the before-
fixed one is free of being restricted in moving, and can move anywhere on I, as
now it acts as the excess covering. Performing such permutation successively will
lead to a rotation, hence CovI(3, 1
4) is homotopy equivalent to a hexagon, or simply
a circle. This is exactly what Theorem 1.2 tells us. On the other hand once iso-
lated points become connected in the configuration space, as the number of excess
covering agents increases from 0 to 1.
[1
2, 3]
[1, 3
2]
[3
1, 2]
[3, 2
1]
[2
1, 3]
[1, 2
3]
123
132
312
321
231
213
1
2
3
3
1
2
Figure 1: Visualization of the covering configuration space for 3 points to cover I
while 2 is enough. The figure shows how the 1 skeleton of permutahedron Π2 can
be thought of as a homotopy equivalence of a hexagon with vertices labelled by
critical configurations, plus 6 triangular cells glued on its edges.
Here we have another point to make, which is a little technical but turns out
to be very helpful in the proof we will present later: there is a one-to-one corre-
spondence between an edge in Skel1(Π2) and a critical configuration point. The
visualization is given in figure 1. The inner hexagon has its vertices labelled by
those critical configurations. Edge is formed when we move the excess agent to
form another critical configuration. Skel1(Π2) (the bigger hexagon) can be recov-
ered first by the expansion of the inner hexagon and then by deformation retracting
to it. We shall make use of this ‘dual’ viewpoint as it helps us identify the critical
configurations while the skeleton of a permutahedron would not naturally do so.
As a more interesting example, the visualization of CovI3(4) is given in figure 2.
Now consider a 2D grid domain G2×2 formed by 2 by 2 square plaques. The
excess agent have the freedom of moving either vertically or horizontally, with
other four covering agents fixed. Its free patrolling region Q is shown in figure 3.
Note that restricting the excess’s move on one edge of ∂Q becomes the problem
of covering 1D line segments, we know CovI(3, 1/2) has the homotopy type of a
hexagon, moving on one edge of ∂Q traverses one edge of the hexagon, so ∂Q can
be glued with Skel1(Π2) along that edge. Let’s identify Q with a 2 by 2 labeling
matrix C, namely, if cij ∈{1, 2, 3, 4, 5} for all i, j = 1, 2, then C is identified with Q;
3
'h
Figure 2: Visualization of the covering configuration space for 4 points with radius
1
6 to cover I (in this case exactly three points cover I just right), on the right is the 1
skeleton of the permutahedron Π3, on the left is the ‘dual’ view.
1
2
3
4
5
Figure 3: Covering a 2 by 2 grid domain with 5 balls B∞(xi, 1
2), the central square
is the region Q where number 5 can move freely.
if C has only three elements from the set {1, 2, 3, 4, 5} specified, then C is identified
with a vertex of Q; if C has only two elements from the set {1, 2, 3, 4, 5} specified
in a row or in a column, then C is identified with a hexagon with one edge on Q.
Tracking the labeling C for cells of different dimensions in Q tells us how Q is glued
in with other parts locally, see figure 4, which forms the subcomplex of CovG2×2(5).
Since Q has free face in CovG2×2(5), therefore, with the removal of 2-cells, the
complex is collapsible to a 1 dimensional complex. We only need to enumerate Q
and hexagons. Therefore, we have 5! Q and 4 × P(5, 2) hexagons. Note that each
edge is shared by one Q and one hexagon, the total number of edge should be (4 ×
5! + 6(4 × P(5, 2)))/2; each vertex is shared by two hexagons (or alternatively, two
Q’s), the total number of vertices should be 4 × 5!/2. Thus, the Euler characteristic
should be
χ(CovX4(5)) = #(Q) −#(edges) + #(vertices) = −5! .
4
Figure 4: The figure on the left illustrates how Q for G2×2 is glued with Skel1(Π2)
and free patrolling regions of different excess covering by choice. Similar visual-
ization can also be done for 3D grid domain G2×2×2. On the right is the gluing for
G2×3.
1.3
MAIN RESULTS
Covering with excess one becomes more complicated in higher dimensions, as the
excess covering can accordingly move freely in higher dimensional regions. In the
sequel we assume the grid domain GA is connected in 2D and is formed by unit
square plaques. The area of RA is A; this implies we can cover GA with exactly A
unit square plaques.
We have proved the following:
Theorem 1.3. Suppose the grid domain GA can be covered precisely by A unit square
plaques, then CovGA(A + 1) is homotopy equivalent to 1 dimensional complex.
Since the essential topological feature of a 1-dimensional complex is determined
by the Euler characteristic, we have also showed that
Theorem 1.4. The Euler characteristic of CovGA(A + 1) is
χ(CovGA(A + 1)) = (χ(GA) −A/2)(A + 1)!,
where χ(GA) is the Euler characteristic for the domain GA.
2
BASICS
Before we give the proof, we begin with some definitions in this section for prepa-
ration.
Definition 2.1. A polyhedral complex P, as a special kind of cell complex, is a collection
of convex polytopes such that
1. every face of a polytope in P is a polytope itself in P;
5
2. the intersection of any two polytopes in P is a face of each of them.
Later we will see that CovGA(A + 1) has the structure of a polyhedral complex.
Definition 2.2. Let P be a polyhedral complex. A free face of P is some τ ∈P such
that there exists one and only one σ ∈P with τ ⊂σ. In particular, dim τ < dim σ. An
elementary collapse of P is the removal of the pair (τ, σ) when dim τ = dim σ −1.
Definition 2.3. A polyhedral complex P1 collapses to another polyhedral complex P2 if
there exists a sequence of elementary collapses, we write P1 ↘P2. An expansion is the
operation inverse to the collapse. We say P1 is the expansion of P2 and write P2 ↗P1.
The following proposition is well-known:
Proposition 2.4. A sequence of collapses yields a strong deformation retraction, in partic-
ular, a homotopy equivalence.
In proving the 2D case, the following labeling notations are given for our con-
venience.
Since each plaque in the 2D domain must be covered by at least one point; in
order to specify particular covering configurations and keep tract of them, we use
CN to define the labeling set
{C =
 c11
c12
...
c1n
...
...
...
...
cm1 cm2 ... cmn

: cij ⊊[N],
G
ij
cij = [N]},
where F stands for disjoint union and [N] denotes the set {1, . . . , N}.
Working on a grid domain GA with arbitrary shape, we shall assume Gm×n
is the minimal rectangular grid domain that covers GA. For the pair of i, j corre-
sponding to square plaque outside GA, we simply ignore cij in that position. Other
cij’s corresponding to positions of different plaques in GA will be active.
Reading off the active cij tells us which point(s) is/are used to cover the plaque
on GA at the ith row and the jth column of the rectangular grid domain Gm×n.
For example, when m = 2, n = 3, N = 7,
h
{1} {3} {2}
{4} {5} {6,7}
i
stands for a covering con-
figuration that points 1, 2, 3, 4, 5 are taking care of their own plaques, while 6, 7
together cover the plaque in the lower right corner. C =
 c11 c12 c13
{4} {5} {6}

with the ac-
tive c11, c12, c13 unspecified corresponds to the situation that we have points 4, 5, 6
covering the second row of plaques, and the first row of plaques are covered up by
points from {1, 2, 3, 7}; in this case, Theorem 1.2 indicates that the minimal covering
configuration space traversing {
 c11 c12 c13
{4} {5} {6}

} has the homotopy type of Skel1(Π3).
Given a covering configuration C=


a11
a12
...
a1n
...
...
...
...
am1 am2 ... amn

, where each aij is a single-
ton except for the inactive ones, the free region Qp for the excess covering agent
p /∈aij is defined as follows:
6
Definition 2.5. The free patrolling region Qp for p is a 2 dimensional polyhedral complex
such that
• the 0-cells v(i,j) corresponds to fixed covering point aij.
• the 1-cells are edges {v(i,j), v(i,j+1)} and {v(i,j), v(i+1,j)} that connect neighboring
covering points.
• the 2-cells are unit square plaques {v(i,j), v(i,j+1), v(i+1,j), v(i+1,j+1)} that are glued
in along its boundary edges.
Remark 1 (On the labeling).
1. Note that there are (A + 1)! such free patrol regions,
since the excess one is identified whenever we have made a choice of the fixed covering
points. It is natural for us to use


a11
a12
...
a1n
...
...
...
...
am1 am2 ... amn

to label Qp.
2. We shall also use


a11
a12
...
a1n
...
...
aij∪{p}
...
am1 am2
...
amn

to label the 0-cell v(i,j). This allows us to
identify different 0-cells on different Qp’s.
In principle, we can use the devised labeling notations to label all the cells in
the complex for the covering configuration space. The right way of gluing for the
covering configuration space means a consistent labeling from cells of 0 dimension
to the working dimension, which shall be made clear in the proof.
Finally, the crossings of Qp are maximal horizontal (resp. vertical) lines travers-
ing the horizontal (resp. vertical) edges. Let the length of a crossing be the number
of vertices on it.
3
PROOF
Construction of CovGA(A + 1):
Our construction of CovGA(A+1) can be described as a gluing process. The basic
idea is to glue the 2 dimensional complex of free patrol region with the 1 skeleton of
permutahedrons along the crossing lines. We shall take advantage of Theorem 1.2,
but in order to facilitate the glueing, we first need to present the modification step
for Skel1(Πn−1):
We denote Skel1(Πn−1) as a polyhedral complex P. In order to ‘patrol’ on the
1 skeleton of permutahedrons, we construct the modification P′ as follows:
1. We first have a barycentric subdivision of P denoted as SP. The mid-points on
each edge of P are 0-cells of SP now.
2. We construct the expansion of SP by adding all pairs (e, t) with e and t satis-
fying the following conditions:
7
• For two edges of P which are connected to a vertex v of P, e is the edge
connecting the mid-points on them.
• t is triangular 2-cell that contains e and the vertex v.
Denote the resulting 2 dimensional polyhedral complex as P′. Since P′ ↗SP, we
immediately have
Lemma 3.1. P′ is homotopy equivalent to P.
This visual change yields advantage in the glueing process. This is because
edges in P corresponds to adjacent transpositions. The mid-points on edges of P
can be used to represent critical covering configurations that two points (the per-
muted pair) are overlapped. The edges in P′ whose boundary are those mid-points
(denoted as evivj) shall be treated as patrolling paths from one critical covering
configuration to another. Indeed, if we look at all the edges in P whose bound-
ary contains the vertex v = 123 · · · n, they (or alternatively, the midpoints) can be
represented as [(12)3 · · · n], [1(23) · · · n], . . . , [123 · · · (n −1, n)], the points in bracket
together cover a fraction of line segment while the others cover one fraction by
themselves. Hence these vertices form a set of critical covering configurations for
the line segment.
There are two types of patrol paths represented by evivj:
• If we take v1 = [(12)3 · · · n], v2 = [1(23) · · · n], ev1v2 represents the path for
point 2 patrolling from 1 to 3. We call such ev1v2 representing a single shift,
denote the set of all single shift edges as E1.
• If we take v1 = [(12)3 · · · n], v2 = [12(34) · · · n], ev1v2 represents the patrol path
for both 2 and 3 synchronously moving to the right from configuration v1 to
v2. This involving more than one point movement, hence we call such ev1v2
representing a swarm shift, denote the set of all swarm shift edges as E2.
When the excess agent travels along crossings of the free patrol region Q, locally
it travels on lines from one critical covering configuration to another, therefore,
edges representing single shift in P′ can be identified with edges in Q.
Now we can describe the glueing process for CovGA(A + 1) as the polyhedral
complex K:
1. Start with the 1-skeleton of Qp for an arbitrary patroller p. Note that there
are (A + 1)! such complexes. On Qp we can list all the crossings. For the ith
crossing on Qp with length n, we have Skel1(P′), where P′ is the expansion
of SSkel1(Πn). The edges on Skel1(P′) that represent single shift shall be
identified with edges on the crossing of Qp. Denote the new space as Ki
p =
Skel1(Qp) ∪E1 Skel1(P′).
2. We glue Ki
p together for different i’s by identifying Skel1(Qp) that is common
to them.
8
3. We glue Kp together for different p’s by identifying the vertices that have the
same label.
4. Finally, glue in the 2-cells of Qp and 2-cells of P′ along their boundaries. The
resulting polyhedral complex ∆is the covering configuration space we are
after.
The reader can refer figure 4 for some illustrations.
Collapsibility:
The important observation of the existence of free edges leads us to the follow-
ing collapsibility:
Lemma 3.2. K is collapsible to a 1-dimension complex.
Sketch of the proof: We prove by giving the sequence of collapse: first for triangular
2-cells in P′: the expansion of 1 skeleton of Πn’s, where n is the length of different
crossings in Qp. When P = Skel1Πn has less than 3! vertices, we can take the
collapsible pair (e,t) with e being the edge with one of its boundary point at a vertex
of P. For P having at least 4! vertices, the expansion P′ has at least one collapsible
pair (e, t) with e not shared by other 2-cells from either P′ or Q. Such e represent
a swarm shift on Q. After the removal of (e, t), edges belonging to the subdivision
of P on t become free. Therefore, we have a sequence of elementary collapses for
all triangular 2-cells in P′.
Note that every Q is identified with some excess agent while the other covering
points are fixed. Permutation only happens when it is overlapped with some other
covering point, therefore, Qp for excess agent p is identified with Qq for excess
agent q by a vertex if and only if they are overlapped at the vertex; the edges on Qp
are never shared by 2-cells from Qq, for q ̸= p. Therefore, working from plaques
with free edges on Qp to plaques surrounded by other plaques, we can have a
sequence of collapses for Qp, leading to 1 dimensional polyhedral complex.
Theorem 1.3 instantly follows. We put the complete proof (using partial match-
ing arguments) in the appendix.
Next, one derives the Euler characteristics by counting the number of cells in
different dimensions.
Note that Qp=


a11
a12
...
a1n
...
...
...
...
am1 am2 ... amn

and Qq=


a′
11
a′
12
...
a′
1n
...
...
...
...
a′
m1 a′
m2 ... a′
mn

are glued by a vertex
if and only if aij = a′
ij for all but one pair of i and j.
Counting:
Combining all the above lemma, we set forward to counting the total number
of cells of K in different dimensions.
Suppose GA is a 2 dimensional domain with Euler characteristic 1 −g, it has
the homotopy type of a disk with g points removed. We have the following lemma
first.
9
Lemma 3.3. Suppose there are ni crossings of length i in total on the free patrolling region
Q and the area of Q is K, χ(GA) = 1 −g, then we have
K = 1 −A +
X
i
ni(i −1) −g.
Proof. Our proof is carried out in two stages: first consider when GA is contractible.
This would allow us to build GA in the following way:
1. beginning from the top row, we construct GA from left to right by adding unit
square blocks one by one.
2. for the next row building, since GA is contractible, we can always pick one
block whose boundary is attaching the first row. We then extend the row by
adding blocks to its left and right. Then we pick another block in this row
attaching to the first row and extend it again. Repeat until we finish building
the second row.
3. repeat the above steps row by row until we complete the last row building.
During the construction, we observe how K is changing when A and the P
i ni(i−
1) terms change. When building the first row of C, adding one block, we have
∆A = 1, ni = 1 and ∆i = 1, K = 0. Note that with ∆A = 1, ∆K = 1 if and only if
a cross emerges in Q. That implies ∆P
i ni(i −1) = 2, by induction, we have
K = 1 −A +
X
i
ni(i −1),
when GA is contractible.
Next, suppose we have holes in GA. We again take the constructional tactic.
The base step is when
G′
A = GA −σs1,
where σs stands for a solid square and GA is contractible, σs1 is in the interior of GA.
We have ∆A = −1, ∆K = −4, and since both the horizontal and vertical crossings
become two shorter crossings, ∆P
i ni(i −1) = −4. Therefore, by induction, if we
remove g isolated blocks in the interior of GA, we have
K = 1 −A +
X
i
ni(i −1) −g.
When enlarging the holes, this equality remains. To see this, we consider all the
possible situations when a generic hole (a missing block in the interior of GA is
enlarged. Suppose a sequential removal of σs1, . . . , σsn leads to an enlarging hole
in GA. ∆A = −1 with σsi+1 removed. Therefore, if σsi ∩σsi+1 is an edge, ∆K = −2,
∆P
i ni(i −1) = −3; if σsi ∩σsi+1 is a vertex, ∆K = −3, ∆P
i ni(i −1) = −4. In
both cases, ∆K = −∆A + ∆P
i ni(i −1). We are done.
10
Now we can prove Theorem 1.4.
Suppose Q has ni crossings with length i, permutation happens only on the
crossing lines. Enumerating the number of cells in different dimensions is similar
to what we have done in last section:
#(σs) = (A + 1)!K,
(1)
where K is the number of σs in Q.
#(σt) =
X
i
P(A + 1, A −i)ni
i(i −1)
2
(i + 1)!
(2)
The triangular 2-cells all come from the expansion of permutahedrons.
#(e) =P
i
(ni −1)(A + 1)! + P
i
P(A + 1, A −i)nii(i + 1)!
+ P
i
P(A + 1, A −i)ni

i(i−1)
2
−(i −1)

(i + 1)!
(3)
The first part comes from edges on Q, the second and third part comes from
edges on the expansion of permutahedrons that are not glued with those on Q.
They belong to swarm shift and edges connecting to the vertices of permutahe-
drons respectively.
#(v) = A
2 (A + 1)! +
X
i
P(A + 1, A −i)ni(i + 1)!
(4)
The first part comes from vertices on Q, each is shared by two Q of different pa-
trollers. The second part comes from vertices of the permutahedrons.
Therefore, combining equations (1)-(4), we have
χ(CovGA(A + 1)) = #(v) −#(e) + #(σs) + #(σt)
=
 
K + A/2 −
X
i
ni (i −1)
!
(A + 1)!.
Together with the lemma, we are done with the proof for 2D domain GA.
4
GENERALIZATION TO 3D
Theorem 1.3 can be generalized to some 3D grid domains with little modification.
3-cells in the free patrolling region Qp for the excess agent p can only share a vertex
for 3-cells in the free patrolling region Qq, where q ̸= p. again, the complex for the
covering configuration space is collapsible to a 1 dimensional complex, as long as
the grid domain itself is collapsible to a 1 dimensional complex. The Euler formula
11
for the 3D case should work similarly as Theorem 1.4. We have worked on some
specific situations: for example, when GA = Ga×b×c, we have
χ(CovGA(A + 1)) = (1 −A/2)(A + 1)!,
where A = abc. When GA has g cavities, it has nontrivial 2 dimensional homology,
we have
χ(CovGA(A + 1)) = (1 + g −A/2)(A + 1)!.
We conjecture that
Conjecture 4.1. The Euler characteristic of CovGA(A + 1) is
χ(CovGA(A + 1)) = (χ(GA) −A/2)(A + 1)!,
where χ(GA) is the Euler characteristic for the domain GA in both 2D and 3D.
But CovGA(A+1) now is not necessarily homotopy equivalent to 1 dimensional
complex in this general setting.
5
CONCLUSIONS
We have studied the problem of covering grid domains with excess one. In this
situation, we are able to find a stunningly simple visualization of the topology of
the covering configuration space. The Euler formula we find establishes a straight
forward relationship between the topology of the space of coverings and the geom-
etry as well as the topology of the working domain. By assuming simple geometric
shape of the domain and a good match with the covering agents, We have man-
aged to utilize combinatorial methods to find the important topological feature of
the covering configuration space. One naturally ask the question: what can we say
about the topology with excess number more than one? To see the topology would
become more complicated, but can we still find some import topological quantity,
say, the total Betti number? We can also ask questions about the unlabeled cover-
ing configuration space. What can we say about the symmetric group action on
the homology group of the covering configuration space? We shall address these
issues in follow-up papers.
6
Acknowledgement
The author wants to thank Prof. Y. Baryshnikov for many inspiring discussions.
12
Appendices
A
Collapsibility
Constructing a sequence of collapses in standard text can be well described using
partial matching defined on a poset (also called discrete vector field by R. Forman,
see [3]), the latter is actually more general than just the elementary collapses. To
begin with this standard treatment, we recognize a polyhedral complex P as a
poset consisting of all the faces and whose partial order relation is the covering
relation on the set of faces, namely, x ≺y if x ⊂y and there is no z ∈P such that
x ⊂z ⊂y.
To describe the structural collapses, we follow the definitions of partial match-
ing from D. Kozlov in [5].
Definition A.1. A partial matching on a poset P is a subset M ⊂P × P such that
1. (a, b) ∈M implies a ≺b;
2. each σ ∈P belongs to at most one element in M.
A partial matching is called acyclic partial matching (ai, bi) ∈M if there does not exist
the following nontrivial closed path
a1 ≺b1 ≻a2 ≺b2 ≻· · · ≻an ≺bn ≻a1
with n ≥2 and all bi being distinct.
Note that a single pair of matching is always acyclic, but they may not be an
elementary collapsable pair. Still, collapsing the matched elements in an acyclic
partial matching will not change the homotopy type of the underlying space.
Our goal is to prove the following lemma:
Lemma A.2. any 2-dimension cell in the polyhedron complex K of our covering configu-
ration space belongs to an element (collapsing pair) in some acyclic matching on P.
Given a 2D grid domain GA, possibly with holes, we can fix all the other cover-
ing agent while allowing one to freely patrol, this enables us to label a subcomplex
Qp of the covering configuration space. All the 2-cells in CovGA(A+1) have exactly
two geometric shapes:
1. square plaques τs: due to planar movement of one single covering agent.
They all come from Qp for some p.
2. triangular plaques τt: due to one dimensional (horizontally or vertically) ro-
tations of multiple covering agent. They all come from the expansions of
certain permutahedrons glued with Qp along its crossings.
13
We describe the matching as follows: for different τt’s, match each with σ ≺τt
satisfying σ /∈∂Qp and preferably choose the σ which is free (not shared by another
τt); if σ /∈∂Qp is not free, we can choose one arbitrarily while avoiding repetitive
matching it with other τt’s.
For different τs’s, we match them in the following way:
• We say a τs is on the boundary if τs has one edge σ on ∂Qp for some p, match τs
with σ. Denote the collection of all the boundary ones as the set M.
• For other τs, if τs ∩τ ̸= ∅, for some τ ∈M, then they must intersect at some edge
σ, match τs with σ. If they intersects at more than one edges, we can pick up an
arbitrary one to match with τs. Update M with all the matched τs’s.
• Repeat the last step until M contains all τs’s.
This partial matching is well-defined and is acyclic. Indeed, every 2-cell can be
matched with their incidental edges without repetition. This relies on the following
observation: for τt, each has at least two edges which are not part of ∂Qp; and at
most two τt’s share an edge. As for τs, each has 4 candidate edges to be matched
with, and at most two τs’s share an edge. Hence each 2-cell can be matched with
one of their incidental edges without repetitive matching with other 2-cells. The
recursive way of matching all τs is valid as essentially any τs is path connected to
one on the boundary.
Next we show it is acyclic. Suppose there exists a sequence σ0, · · · , σt such
that all σi are different except σt = σ0, each σi is matched with some 2-cell, they
form a nontrivial closed path. Then we claim σ0 cannot be an incidental edge of
any τt, the triangular 2-cells. Indeed, first σ0 cannot be a free edge of some τt, since
otherwise τt ≻σ0 has to appear in the matching at least twice, which is not allowed
by the definition of partial matching. Secondly, for other σ0 /∈∂Qp, suppose it is
shared by two triangular 2-cells, to make it a closed path, we have to make the two
cells the first and the last one respectively in the closed path, this is only possible
when we include all the triangular cells which share a single vertex (vertex of the
permutahedron) in the closed path, thus all τt’s has to be matched with shared
edges, yet by construction, we know at least one triangular cell is matched with a
free edge, as free edges always exist in some τt. Finally, σ0 ≺τt cannot be edge
on Qp , this case is obvious as such σ0 can only be matched with some τs on the
boundary, according to our scheme; the only chance to get back is having some τt
in the closed path, which is impossible.
What remains to be proved is that σ0 can not be any interior edge of Qp, for
any p. By the inductive construction, we can draw a path connecting the sequence
σ0, · · · , σt all the way to an edge on the boundary, this contradicts with the path
being closed. We are done.
14
References
[1] Yuliy Baryshnikov, Peter Bubenik, and Matthew Kahle. Min-type morse the-
ory for configuration spaces of hard spheres. International Mathematics Research
Notices, 2013.
[2] Subhrajit Bhattacharya, Nathan Michael, and Vijay Kumar. Distributed cov-
erage and exploration in unknown non-convex environments.
In Proceed-
ings of 10th International Symposium on Distributed Autonomous Robotics Systems.
Springer, 1-3 Nov 2010.
[3] Robin Forman. Morse theory for cell complexes. Adv. Math., 134(1):90–145,
1998.
[4] Peter Hall. Introduction to the theory of coverage processes. Wiley Series in Proba-
bility and Mathematical Statistics: Probability and Mathematical Statistics. John
Wiley & Sons Inc., New York, 1988.
[5] Dmitry Kozlov. Combinatorial algebraic topology, volume 21 of Algorithms and
Computation in Mathematics. Springer, Berlin, 2008.
[6] L. C A Pimenta, V. Kumar, R.C. Mesquita, and G. A S Pereira. Sensing and
coverage for a network of heterogeneous robots. In Decision and Control, 2008.
CDC 2008. 47th IEEE Conference on, pages 3947–3952, 2008.
[7] Andrew Chi-Chih Yao. Decision tree complexity and Betti numbers. J. Comput.
System Sci., 55(1, part 1):36–43, 1997. 26th Annual ACM Symposium on the
Theory of Computing (STOC ’94) (Montreal, PQ, 1994).
[8] G¨unter M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathe-
matics. Springer-Verlag, New York, 1995.
15