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  Cov X   ( n,   F ) :=   { ( f 1 , f 2 , . . . , f n ) , f i   ∈   F   :  n ⋃  i =1  M f i   =   X } ,  where   F   is a topological space parametrizing subsets of   X   as   { M f   } 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   Cov G N   ( N   + 1) , where   G N   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   Cov I   ( n, r )  as the covering configuration space for unit interval   I   with   n   balls of radii   r , we have  Theorem 1.2   (Y. Baryshnikov) .  Cov I   ( n, r )   ' h   Skel k (Π n − 1 ) ,  where   Π n − 1   is the permutahedron with each vertice coresponding to a permutation of  (1 , . . . , n ) ,   k   =   n   − d   1 2 r   e   and   d   1 2 r   e   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  Cov I N   ( N   + 1)   ' h   Skel 1 (Π 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,   Cov I   (3 , r )   changes. The trivial case happens when   r   is sufficently large, say,   r   =   1 2   , then   Cov I   (3 , r )   is contractible to a point. On the other extreme case, when   r   is too small,   Cov I   (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,   Cov I   (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   Cov I   (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   Skel 1 (Π 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.   Skel 1 (Π 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   Cov I 3   (4)   is given in figure 2. Now consider a 2D grid domain   G 2 × 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   Cov I   (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   Skel 1 (Π 2 )   along that edge. Let’s identify   Q   with a   2   by   2   labeling matrix   C , namely, if   c ij   ∈ { 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 ∞ ( x i ,   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   Cov G 2 × 2   (5) . Since   Q   has free face in   Cov G 2 × 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  χ ( Cov X 4   (5)) = #( Q )   −   #( edges ) + #( vertices ) =   − 5!   .  4
Figure 4: The figure on the left illustrates how   Q   for   G 2 × 2   is glued with   Skel 1 (Π 2 )  and free patrolling regions of different excess covering by choice. Similar visual- ization can also be done for 3D grid domain   G 2 × 2 × 2 . On the right is the gluing for  G 2 × 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   G A   is connected in 2D and is formed by unit square plaques. The area of   R A   is   A ; this implies we can cover   G A   with exactly   A  unit square plaques. We have proved the following:  Theorem 1.3.   Suppose the grid domain   G A   can be covered precisely by   A   unit square plaques, then   Cov G A   ( 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   Cov G A   ( A   + 1)   is  χ ( Cov G A   ( A   + 1)) = ( χ ( G A )   −   A/ 2)( A   + 1)! ,  where   χ ( G A )   is the Euler characteristic for the domain   G A .  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   Cov G A   ( 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   P 1   collapses   to another polyhedral complex   P 2   if there exists a sequence of elementary collapses, we write   P 1   ↘ P 2 . An   expansion   is the operation inverse to the collapse. We say   P 1   is the expansion of   P 2   and write   P 2   ↗ P 1 .  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  C N   to define the labeling set  { C   =  [   c 11   c 12   ...   c 1 n  . . .   . . .   ...   . . .  c m 1   c m 2   ...   c mn  ]  :   c ij   (   [ N   ] ,   ⊔  ij  c ij   = [ N   ] } ,  where   ⊔   stands for disjoint union and   [ N   ]   denotes the set   { 1 , . . . , N   } . Working on a grid domain   G A   with arbitrary shape, we shall assume   G m × n  is the minimal rectangular grid domain that covers   G A . For the pair of   i, j   corre- sponding to square plaque outside   G A , we simply ignore   c ij   in that position. Other  c ij   ’s corresponding to positions of different plaques in   G A   will be   active . Reading off the active   c ij   tells us which point(s) is/are used to cover the plaque on   G A   at the   i th row and the   j th column of the rectangular grid domain   G m × n . For example, when   m   = 2 , n   = 3 , N   = 7 ,  [   { 1 } { 3 }   { 2 } { 4 } { 5 } { 6 , 7 }  ]  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   =   [   c 11   c 12   c 13  { 4 } { 5 } { 6 }  ]   with the ac- tive   c 11 , c 12 , c 13   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   { [   c 11   c 12   c 13  { 4 } { 5 } { 6 }  ] }   has the homotopy type of   Skel 1 (Π 3 ) . Given a covering configuration   C =     a 11   a 12   ...   a 1 n  . . .   . . .   ...   . . .  a m 1   a m 2   ...   a mn    , where each   a ij   is a single- ton except for the inactive ones, the free region   Q p   for the excess covering agent  p / ∈   a ij   is defined as follows: 6
Definition 2.5.   The   free patrolling region   Q p   for   p   is a   2   dimensional polyhedral complex such that  •   the   0 -cells   v ( i,j )   corresponds to fixed covering point   a ij   .  •   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     a 11   a 12   ...   a 1 n  . . .   . . .   ...   . . .  a m 1   a m 2   ...   a mn      to label   Q p . 2. We shall also use     a 11   a 12   ...   a 1 n  . . .   . . .   a ij   ∪{ p }   . . .  a m 1   a m 2   ...   a mn      to label the   0 -cell   v ( i,j ) . This allows us to identify different   0 -cells on different   Q p ’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   Q p   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   Cov G A   ( A   + 1) : Our construction of   Cov G A   ( 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   Skel 1 (Π n − 1 ) : We denote   Skel 1 (Π 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   S P . The mid-points on each edge of   P   are   0 -cells of   S P   now. 2. We construct the expansion of   S P   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 ′   ↗   S P , 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   e v i v j   ) 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   e v i v j   :  •   If we take   v 1   = [(12)3   · · ·   n ] ,   v 2   = [1(23)   · · ·   n ] ,   e v 1 v 2   represents the path for point   2   patrolling from   1   to   3 . We call such   e v 1 v 2   representing a   single shift , denote the set of all single shift edges as   E 1 .  •   If we take   v 1   = [(12)3   · · ·   n ] ,   v 2   = [12(34)   · · ·   n ] ,   e v 1 v 2   represents the patrol path for both   2   and   3   synchronously moving to the right from configuration   v 1   to  v 2 . This involving more than one point movement, hence we call such   e v 1 v 2  representing a   swarm shift , denote the set of all swarm shift edges as   E 2 . 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   Cov G A   ( A   + 1)   as the polyhedral complex   K : 1. Start with the   1 -skeleton of   Q p   for an arbitrary patroller   p . Note that there are   ( A   + 1)!   such complexes. On   Q p   we can list all the crossings. For the   i th crossing on   Q p   with length   n , we have   Skel 1 ( P ′ ) , where   P ′   is the expansion of   S Skel 1 (Π n ) .   The edges on   Skel 1 ( P ′ )   that represent single shift shall be identified with edges on the crossing of   Q p . Denote the new space as   K i p   =  Skel 1 ( Q p )   ∪ E 1   Skel 1 ( P ′ ) . 2. We glue   K i p   together for different   i ’s by identifying   Skel 1 ( Q p )   that is common to them. 8
3. We glue   K p   together for different   p ’s by identifying the vertices that have the same label. 4. Finally, glue in the   2 -cells of   Q p   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   Q p .   When   P   =   Skel 1 Π 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,   Q p   for excess agent   p   is identified with   Q q   for excess agent   q   by a vertex if and only if they are overlapped at the vertex; the edges on   Q p  are never shared by 2-cells from   Q q , for   q   6   =   p . Therefore, working from plaques with free edges on   Q p   to plaques surrounded by other plaques, we can have a sequence of collapses for   Q p , 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   Q p =     a 11   a 12   ...   a 1 n  . . .   . . .   ...   . . .  a m 1   a m 2   ...   a mn      and   Q q   =      a ′  11   a ′  12   ...   a ′  1 n  . . .   . . .   ...   . . .  a ′  m 1   a ′  m 2   ...   a ′  mn       are glued by a vertex if and only if   a ij   =   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   G A   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   n i   crossings of length   i   in total on the free patrolling region  Q   and the area of   Q   is K,   χ ( G A ) = 1   −   g , then we have  K   = 1   −   A   +   ∑  i  n i ( i   −   1)   −   g.  Proof.   Our proof is carried out in two stages: first consider when   G A   is contractible. This would allow us to build   G A   in the following way: 1. beginning from the top row, we construct   G A   from left to right by adding unit square blocks one by one. 2. for the next row building, since   G A   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   ∑  i   n i ( i −  1)   terms change.   When building the first row of   C , adding one block, we have  ∆ A   = 1 ,   n i   = 1   and   ∆ i   = 1 ,   K   = 0 . Note that with   ∆ A   = 1 ,   ∆ K   = 1   if and only if a cross emerges in   Q . That implies   ∆   ∑  i   n i ( i   −   1) = 2 , by induction, we have  K   = 1   −   A   +   ∑  i  n i ( i   −   1) ,  when   G A   is contractible. Next, suppose we have holes in   G A . We again take the constructional tactic. The base step is when  G ′  A   =   G A   −   σ s 1   ,  where   σ s   stands for a solid square and   G A   is contractible,   σ s 1   is in the interior of   G A . We have   ∆ A   =   − 1 ,   ∆ K   =   − 4 , and since both the horizontal and vertical crossings become two shorter crossings,   ∆   ∑  i   n i ( i   −   1) =   − 4 . Therefore, by induction, if we remove   g   isolated blocks in the interior of   G A , we have  K   = 1   −   A   +   ∑  i  n i ( 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   G A   is enlarged. Suppose a sequential removal of   σ s 1   , . . . , σ s n   leads to an enlarging hole in   G A .   ∆ A   =   − 1   with   σ s i +1   removed. Therefore, if   σ s i   ∩   σ s i +1   is an edge,   ∆ K   =   − 2 ,  ∆   ∑  i   n i ( i   −   1) =   − 3 ; if   σ s i   ∩   σ s i +1   is a vertex,   ∆ K   =   − 3 ,   ∆   ∑  i   n i ( i   −   1) =   − 4 . In both cases,   ∆ K   =   − ∆ A   + ∆   ∑  i   n i ( i   −   1) . We are done. 10
Now we can prove Theorem 1.4. Suppose   Q   has   n i   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 ) =   ∑  i  P   ( A   + 1 , A   −   i ) n i  i ( i   −   1) 2   ( i   + 1)!   (2) The triangular 2-cells all come from the expansion of permutahedrons.  #( e ) = ∑  i  ( n i   −   1)( A   + 1)! +   ∑  i  P   ( A   + 1 , A   −   i ) n i i ( i   + 1)! +   ∑  i  P   ( A   + 1 , A   −   i ) n i  (   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)! +   ∑  i  P   ( A   + 1 , A   −   i ) n i ( 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  χ ( Cov G A   ( A   + 1)) = #( v )   −   #( e ) + #( σ s ) + #( σ t ) =  (  K   +   A/ 2   −   ∑  i  n i   ( i   −   1)  )  ( A   + 1)! .  Together with the lemma, we are done with the proof for 2D domain   G A .  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   Q p   for the excess agent   p   can only share a vertex for 3-cells in the free patrolling region   Q q , where   q   6   =   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   G A   =   G a × b × c , we have  χ ( Cov G A   ( A   + 1)) = (1   −   A/ 2)( A   + 1)! ,  where   A   =   abc . When   G A   has   g   cavities, it has nontrivial 2 dimensional homology, we have  χ ( Cov G A   ( A   + 1)) = (1 +   g   −   A/ 2)( A   + 1)! .  We conjecture that  Conjecture 4.1.   The Euler characteristic of   Cov G A   ( A   + 1)   is  χ ( Cov G A   ( A   + 1)) = ( χ ( G A )   −   A/ 2)( A   + 1)! ,  where   χ ( G A )   is the Euler characteristic for the domain   G A   in both 2D and 3D.  But   Cov G A   ( 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   ( a i , b i )   ∈   M   if there does not exist the following nontrivial closed path  a 1   ≺   b 1      a 2   ≺   b 2    · · ·    a n   ≺   b n      a 1  with   n   ≥   2   and all   b i   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   G A , 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  Q p   of the covering configuration space. All the   2 -cells in   Cov G A   ( A   + 1)   have exactly two geometric shapes: 1. square plaques   τ s : due to planar movement of one single covering agent. They all come from   Q p   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   Q p   along its crossings. 13
We describe the matching as follows: for different   τ t ’s, match each with   σ   ≺   τ t  satisfying   σ / ∈   ∂ Q p   and preferably choose the   σ   which is free (not shared by another  τ t ); if   σ / ∈   ∂ Q p   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   ∂ Q p   for some   p , match   τ s  with   σ . Denote the collection of all the boundary ones as the set   M   .  •   For other   τ s , if   τ s   ∩   τ   6   =   ∅ , 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   ∂ Q p ; 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   / ∈   ∂ Q p , 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   Q p   , 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   Q p , 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