David Ilcinkas

Ahmed M Wade

Exploration of carrier-based time-varying networks: the power of waiting $

Keywords: Exploration, Dynamic graphs, Mobile agent, C-graph

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n-node C-graph of k carriers and maximal period p is in Θ(kp 2 ) in the general case.

In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ(p), while the worst-case time complexity is reduced to Θ(np). (In any connected carrier graph, we have n ≤ kp.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it.

Introduction

The problem

The problem of graph exploration consists, for a mobile entity, in exploring all nodes (or edges) of an a priori unknown graph. This problem being one of the most classical in the mobile agent computing framework, it has received a lot of attention so far. Time complexity, space complexity, or impact of a priori knowledge have extensively been studied in the last 40 years (see, e.g., [START_REF] Dessmark | Optimal graph exploration without good maps[END_REF][START_REF] Panaite | Exploring Unknown Undirected Graphs[END_REF][START_REF] Reingold | Undirected connectivity in log-space[END_REF]). However, the large majority of these works concern static graphs. Considering networks nowadays, it is now common to deal with dynamic networks. In this paper, we study the graph exploration problem in a particular class of time-varying graphs namely the carrier graph (C-graph) model (the C-graphs were called PV-graphs in the first papers concerning them).

Roughly speaking, a C-graph consists of a set of carriers, each following periodically its respective route among the sites of the system. This models in particular various types of public transportation systems like bus systems or subway systems for example. It also models low earth orbiting satellite systems, or security systems composed of security guards making tours in the place to be secured. Performing exploration in such systems may be useful for maintenance operations for example. Indeed, an agent can check that everything is in order during the exploration. This agent may be a piece of software, or a human being.

The exploration problem in the C-graph model was already considered by Flocchini, Mans, and Santoro in [START_REF] Flocchini | On the exploration of timevarying networks[END_REF]. They considered that the agent cannot leave the carrier to stay on a site. Not being able to stay on a site is particularly legitimate in low earth orbiting satellite systems for example, where the sites do not correspond to any physical station. However, in most public transportation systems, it is possible for the agent (human or not) to stay on a site in order to wait for a (possibly different) carrier. In this paper, we consider the same problem but in the case when the agent can leave carriers to wait on a site. We study the impact of this new ability on the worst-case complexity (time and number of moves) of the C-graph exploration problem.

Related work

Motivated by the automatic exploration of the Web, Cooper and Frieze [START_REF] Cooper | Crawling on simple models of web graphs[END_REF] studied the question of the minimum cover time of a graph that evolves over time. They considered a particular model of so-called web graphs and showed that if after every constant number of steps of the walk a new node appears and is connected to the graph, a random walk does not visit a constant fraction of nodes. Avin, Koucky and Lotker [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF] showed that a random walk may have an exponential cover time in some dynamic graphs. They also show that a variant, the lazy random walk, has however a polynomial cover time in any dynamic graph.

To investigate distributed computations in dynamic networks, Kuhn, Lynch and Oshman [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] introduced a new stability property called T -intervalconnectivity, for a given positive integer T . This property ensures that for any T consecutive rounds, there is a stable and connected common subgraph.

Considering this stability property, Ilcinkas and Wade studied the complexity of the exploration of dynamic rings by a mobile agent [START_REF] Ilcinkas | Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF]. The same stability property, with T = 1, is also considered by Di Luna, Dobrev, Flocchini, and Santoro in [START_REF] Di Luna | Distributed exploration of dynamic rings[END_REF] to study the decentralized (or live) exploration of a dynamic ring by a team of agents.

Casteigts, Flocchini, Santoro and Quattrociocchi [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF] integrated a large collection of concepts, formalisms and results in the literature about dynamic graphs in an unified space called time-varying graphs. Flocchini, Mans and Santoro [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] introduced a specific class of time-varying graphs, the C-graph model. They first show that if the nodes of the C-graph are labeled, the knowledge of an upper bound on the longest period or the exact knowledge of the number n of nodes is necessary and sufficient for an agent to explore the C-graph. If the nodes of the C-graph are anonymous, then the knowledge of an upper bound on the longest period is necessary and sufficient. In both settings, the worst-case time and move complexity of the agent is proved to be in Θ(kp 2 ), where k is the number of carriers and p the maximum period of the carriers. In the particular case of homogeneous C-graphs (C-graphs for which all carriers have the same period), the worst-case time and move complexity drops to Θ(kp).

Using a C-graph to model an urban subway system with black holes (sites destroying agents), Flocchini, Kellett, Mason, and Santoro [START_REF] Flocchini | Searching for black holes in subways[END_REF][START_REF] Flocchini | Finding Good Coffee in Paris[END_REF] examined the problem of constructing a map of such a subway. They considered that several agents are operating in the C-graph, and that they can leave messages on the sites. The goal of the agents is to construct the map of the C-graph without losing too many agents. The class of C-graphs is also used in [START_REF] Brejová | Efficient routing in Carrier-Based Mobile Networks[END_REF],

where the authors consider oblivious carriers and investigate the routing problem.

Our results

In this article, we extend the study of Flocchini, Mans and Santoro [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] to the case when the agent can leave a carrier to stay at a site. This new ability allows the agent to explore C-graphs that are less connected over time (formal definitions are given in Section 2). We prove that in the general case (so, even considering non highly-connected C-graphs) the worst-case move complexity is reduced to Θ(min{kp, np, n 2 }), while the worst-case time complexity decreases to Θ(np). (Note that in any connected C-graph, we have n ≤ kp.) If the C-graphs are restricted to be both homogeneous and highly-connected, then Flocchini, Mans and Santoro proved that the worstcase time complexity is in O(kp). In this paper, we prove that if the C-graphs satisfy only one of these restrictions, then the worst-case time complexity remains in Θ(np). Besides, it turns out that our algorithm not only performs exploration but also performs mapping, i.e., it can output an isomorphic copy of the C-graph. Finally, note that our algorithm does not use possible identifiers of the nodes, while all our lower bounds still hold when the agent has access to unique node identifiers.

Results from [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] Connected Highly-connected Our results

Not necessarily

Impossible Θ(kp [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] (top of each cell, in blue color). All mentioned complexities are asymptotic worst-case complexities.

Model and definitions

We consider a system S = {s 1 , • • • , s n } of n sites among which k carriers are moving. Each carrier c has an identifier Id(c) and follows a finite sequence

R(c) = (s i 1 , • • • , s i p(c)
) of sites, called its route, in a periodic manner. The positive integer p(c) is called the period of the carrier c. More precisely, the carrier c starts at node s i 1 at time 0 and then proceeds along its route, moving to the next site at each time unit, in a cyclic manner (that is, when c is at node s i p(c) , it goes back to s i 1 and follows the route again and again).

A [START_REF] Flocchini | On the exploration of timevarying networks[END_REF], the agent is allowed to leave a carrier, stay at the current site, and get back on a carrier (the same or another).

We do not assume any restriction on the memory size of the agent or on its computational capabilities. We consider two models concerning the nodes' identities. In an anonymous C-graph, the nodes do not have any identities, or the agent is not able to see them. In a labeled C-graph, the nodes have distinct identities and the agent can see and memorize them.

We say that an agent explores a C-graph if and only if, starting at time 0 on the starting site of the first carrier (this can be assumed without loss of generality), the agent eventually visits all sites of the C-graph and switches afterwards to a terminal state. This terminal state expresses the fact that the agent knows that exploration has been completed.

Solvability

Similarly as in the case when the agent cannot wait, an agent without information on the C-graphs it has to explore cannot explore all C-graphs (even if restricted to the labeled homogeneous highly-connected ones).

Theorem 1. There exists a family of labeled homogeneous highly-connected C-graphs such that no agent can explore all the graphs of this family if it has no information on the C-graphs it has to explore.

Sketch of proof. Intuitively, the family consists of a small C-graph G 0 and an infinity of C-graphs "looking like" G 0 for an arbitrarily large time. The agent must enter to a terminal state in a finite time t after completing the exploration of G 0 . It is possible to prove that there is a C-graph of the family that the agent will not be able to differentiate from G 0 until time t + 1 and that has one more site, which will never be explored by the agent.

Proof. Let S = {s 1 , s 2 , s 3 } be a set of three sites with distinct IDs. For t > 0, we define the C-graph G t over the set S of sites composed of a single carrier. Its route is (s 1 , s 2 , . . . , s 1 , s 2 , s 1 , s 2 , s 3 ), where (s 1 , s 2 ) is repeated exactly t times. Moreover, let G 0 be the C-graph over the set of sites {s 1 , s 2 } composed of a single carrier, whose route is (s Assume, for the purpose of contradiction, that there exists an algorithm solving the exploration problem in all the C-graphs in G, provided that the agent A running this algorithm does not receive any additional information.

1 , s 2 ). The family {G 0 , G 1 , . . . } is denoted G, see Figure 1. 1 2 s 1 s 1 s 2 s 2 s 3 1, 3, . . . , 2t + 1 2t + 2 2t + 3 2, 4, . . . , 2t
In particular, A explores G 0 . Let t be the time at which A switches to the terminal state. Assume now that A is placed in G t . For the first t time units, A cannot tell the difference between G 0 and G t , because A has no information about the C-graph it has to explore and in particular it does not know the number of sites or an upper bound on the system period. It will therefore act exactly the same in G t as in G 0 . In particular, it will switch to the terminal state at time t although the site s 3 has not yet been explored.

This contradiction concludes the proof.

General case

In this section, we make no assumption on the C-graphs (except the connectedness assumption of course). We basically show that the ability to wait allows the agent to explore, and even map, all connected C-graphs (not only the highly-connected ones), provided that the agent knows for each of them an upper bound on its maximal period. This can be done in only Θ(min{kp, np, n 2 }) moves in the worst case, that is, at least p times less than when the agent cannot wait. Besides, the worst-case time complexity is reduced from Θ(kp 2 ) to Θ(np).

Lower bound on the number of moves

Flocchini, Mans and Santoro [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] proved a lower bound Ω(kp) on the number of moves to explore the C-graphs with k carriers and maximum period p (even if restricted to the labeled homogeneous highly-connected ones). This lower bound does not apply directly in our setting because the agent, having the possibility to wait, could potentially be able to explore in significantly less moves. We will prove later that this is actually the case: the move complexity of our algorithm is bounded by O(min{kp, np, n 2 }). We prove here that this complexity is optimal. (If n < 16, then the third term of the minimum is obviously a lower bound.)

We consider two cases.

Case 1: p ≤ 3n 2 16k .

Let us first assume that k ≤ n/8 and let q = n 2k . Note that p/2 ≥ q ≥ 4.

We denote by r the non-negative integer p/q q -p. Let S = {s 1 , s 2 , . . . , s n } be a set of n sites. We partition S into the sets S 0 and S i,j , with 1 ≤ i ≤ k and 1 ≤ j ≤ q, such that:

• S 0 = {s 1 , s 2 , . . . , s p/q -1 } and S 1,1 = {s p/q }; • For all 1 ≤ i ≤ k and 1 ≤ j ≤ q, we have S i,j = ∅; • For all 2 ≤ i ≤ k, we have |S i,1 | ≤ p/q -1;
• For all 1 ≤ i ≤ k and 2 ≤ j ≤ q -r, we have |S i,j | ≤ p/q ;

• For all 1 ≤ i ≤ k and q -r < j ≤ q, we have |S i,j | ≤ p/q -1;

• While respecting the previous bounds on the size of the sets S i,j , we have that if some S i,j has not its maximum, resp. minimum, allowed size, then all sets S i ,j , with (i , j ) lexicographically larger, resp.

smaller, than (i, j), have their minimum, resp. maximum, allowed size. Such a partition is always possible, for the following reasons. First, p and k being fixed, the maximum number of sites permitting the construction is obtained when all sets S i,j have their maximum allowed size. This leads to the inequality

n ≤ ( p/q -1) + 1 + (k -1)( p/q -1) + k(q -1 -r) p/q + kr( p/q -1)
which is equivalent to the connectivity condition n ≤ p + (k -1)(p -1), by definition of r. Second, still with p and k fixed, the minimum number of sites permitting the construction is obtained when all sets S i,j have size 1. This leads to the inequality n ≥ ( p/q -1) + kq which is implied by the condition p ≤ 3n 2 16k . Indeed, this condition implies that

p ≤ n 4k (n -2k) = n 2 ( n 2k -1), because k ≤ n/8. We thus have p ≤ n 2 n 2k = n 2 q,
by definition of q. Rearranging the inequality, we obtain n 2 + 1 ≥ p q + 1 ≥ p q .

Finally, we obtain n ≥ ( p q -1) + k n 2k ≥ ( p q -1) + kq, as desired.

The C-graph G n,k,p is now defined as follows, see Fig. 2. Let S be its set of sites and C = {c 1 , c 2 , . . . , c k } be the set of its carriers. For every

1 ≤ i ≤ k, the route R(c i ) is defined as follows.
The route starts at s 1 at time 0 and then visits s 2 , s 3 , • • • , s l , with l = p/q -|S i,1 |, followed by each site of the set S i,1 . (When l = 1, the route goes directly from s 1 to the sites of S i,1 .) The route continues by visiting, for successive values of j from 2 to q, the sites

s 1 , s 2 , • • • , s l , with l = p/q -|S i,j | (or l = p/q -1 -|S i,j |
if j > q -r), followed by each site of the set S i,j . (When l = 0, the route directly continues to S i,j , without going through any site in S 0 .) Note that G n,k,p is both homogeneous (of period p) and highly-connected (because s 1

is the starting site of all routes).

The C-graph G n,k,p is constructed in such a way that the agent basically has to follow each carrier's route entirely to visit all sites. More precisely, to visit the sites of any set S i,j and to come back to s 1 , the agent has to pay p/q moves ( p/q -1 if j > q -r). Hence the minimum number of moves an exploring agent has to perform in G n,k,p is kp -1.

Now assume that k > n/8. In this case, we simply use the above construction for n/8 carriers. All carriers c i , with i > n/8 are given the same route as c 1 . This gives the lower bound n/8 p -1.

Case 2: p > 3n 2 16k .

First assume that k ≤ n/16. The C-graph G n,k,p is defined in this case as follows, see Fig. 3. Let C = {c 1 , c 2 , . . . , c k } be the set of its carriers and let S = {s 1 , s 2 , . . . , s n } be the set of its sites, partitioned in S 0 = {s 1 , s 2 , . . . , s n-n/8 } and S 1 = S \ S 0 . The set S 1 is further partitioned into the sets S 1,1 to S 1,k of weakly increasing size such that the sizes of any two sets differs by at most one (differently speaking, the size of a set S 1,i It finally stays in s i l so that its period is exactly p. In order for the construction to be possible, the maximum period p must satisfy p ≥ (n -n/8 + 1) n/8 /k which is implied by the condition p > 3n 2 16k when k ≤ n/16. Note that G n,k,p is both homogeneous (of period p) and highly-connected (because s 1 is the starting site of all routes).

is either |S 1 |/k or |S 1 |/k ). If S 1,i = {s i 1 , s i 2 ,
By construction, all sites in S 1 are only accessible through s n-n/8 and the agent can only leave them by going to s 1 with some carrier. Again by construction, any agent willing to go from s 1 to s n-n/8 has to go through all the sites s 1 , s 2 , . . . , s n-n/8 . Therefore, for any i, j such that 1 ≤ i = j ≤ n/8 , going from s n-i+1 to s n-j+1 requires any agent to perform at least n -n/8 + 1 moves. Since any agent performing exploration of the C-graph must visit all its sites, any agent requires at least (n -n/8 + 1)( n/8 -1) moves to explore G n,k,p . Now assume that k > n/16. In this case, we simply use the above construction for n/16 carriers. All carriers c i , with i > n/16 are given the same route as c 1 . This gives the same lower bound 7n/8( n/8 -1).

Summarizing the previous lemma by considering the asymptotic behavior, we directly obtain the following theorem.

Theorem 2. The worst-case move complexity of the C-graph exploration problem is in Ω(min{kp, np, n 2 }), where n, k, and p denote respectively the number of sites, the number of carriers, and the maximal period. This result holds even if the agent knows completely the C-graph, has unlimited memory, and even in the labeled homogeneous highly-connected case.

Lower bound on time

We prove a larger lower bound for the worst-case time complexity than for the worst-case move complexity in the general case. More precisely, we have the following lemma. Fix any u 1 , . . . , u k-1 and t 2 , . . . , t k such that, for every 1

≤ i ≤ k -1, we have u i ∈ S i and 1 ≤ t i+1 ≤ p. The C-graph G((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u k-1 , t k ))
is defined as follows.

Let u 0 = s 1 and t 1 = 0. Consider any i such that 1 ≤ i ≤ k. The route R(c i ) is any route of period p going through (and only through) all the sites in S i ∪{u i-1 } satisfying the following two conditions. First, c i visits u i-1 only once per period, at all times equal to t i modulo p. Second, the route R(c i )

does not depend on the values u l and t l+1 , for l = i -1. Such a construction is possible thanks to the connectivity condition n ≤ p + (k -1)(p -1).

We denote G n,p,k the family of all C-graphs G((u 1 , t 2 ), . . . , (u k-1 , t k )) with, for every 1 ≤ i ≤ k -1, u i ∈ S i and 1 ≤ t i+1 ≤ p. All these C-graphs are labeled homogeneous connected C-graphs with n sites, k carriers and period p.

Let A be any exploring agent (i.e. executing any exploration algorithm).

Given 1 ≤ i ≤ k and a C-graph G of G n,p,k , let T i (G) be the first time at which the agent A, starting at s 1 at time 0 in G, sees the carrier c i . Given q, 1 ≤ q ≤ k, and u 1 , u 2 , . . . , u q-1 and t 2 , t 3 , . . . , t q in the usual ranges, we define G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) as the set of all the C-graphs G((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u k-1 , t k )) with, for every q ≤ i ≤ k -1, u i ∈ S i and 1 ≤ t i+1 ≤ p.

Claim 1. For every q, 1 ≤ q ≤ k, there exist u i and t i+1 satisfying u i ∈ S i and 1 ≤ t i+1 ≤ p for every i, 1 ≤ i ≤ q -1, such that for every graph

G ∈ G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) we have T q (G) ≥ p q-1 i=1 |S i |.
Proof of the Claim: We prove the claim by induction on q. The base case q = 1 is trivially true. Fix any q such that 1 ≤ q ≤ k -1, and assume, by induction hypothesis, that the claim holds for the value q.

Let G q be the family G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) whose existence is guaranteed by the induction hypothesis. Note that all C-graphs in G q have exactly the same routes R(c i ), for 1 ≤ i ≤ q. We can thus define H q to be the C-graph consisting only of the carriers c 1 to c q of any C-graph in G q . Let us consider now the agent A starting at s 1 at time 0 in H q . By induction hypothesis and by construction of H q , the agent A sees c q for the first time at time t with t ≥ p q-1 i=1 |S i | time units. Thus there exists u q and t q+1 satisfying u q ∈ S q and 1 ≤ t q+1 ≤ p such that A is never at u q at a time equal to t q+1 modulo p before time t + p|S q |, and thus before time p q i=1 |S i |.

Consider now the agent A starting at s 1 at time 0 in any C-graph G in G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q ), (u q , t q+1 )). Before time p q i=1 |S i |, the agent will behave exactly the same as in H q and will not see the carrier c q+1 .

This concludes the proof of the claim. ♦

The lemma follows by considering the claim for the last value q = k, and removing the assumption k ≤ n -1.

Again, summarizing the previous lemma by considering the asymptotic behavior, we directly obtain the following theorem.

Theorem 3. The worst-case time complexity of the C-graph exploration problem is in Ω(np) in the general case (for k ≥ 2). This result holds even if the agent knows n, k, and p, has unlimited memory, and even in the labeled homogeneous (connected) case.

Our algorithm

In the above part of the paper, we exhibited some necessary conditions on the existence of a solution. We then provided lower bounds on the worst-case move and time complexities. We now essentially prove that all these results are optimal by describing and proving a C-graph exploration algorithm with matching upper bounds on the move and time complexities, provided that the agent knows a linear upper bound B on the maximum period p. As a consequence, we show that the ability to wait allows to decrease both the worst-case move and time complexities, the former by a multiplicative factor at least Θ(p).

Principle

As previously specified, our algorithm uses an upper bound B on the largest period p of the C-graph (cf. Theorem 3). The main idea of the algorithm consists of getting off on each site and, during Θ(B) time units, to note each visit of the carriers at the site. Properly managed, this information allows to map the C-graph (i.e., to list the routes and times of passage of all carriers).

Several precautions must be taken into account in order not to miss any site and to optimize the number of moves. For example, after each study of a site (during Θ(B) time units), the algorithm computes the smallest possible period of each seen carrier by using the already collected information. This allows to know all the future passing times of the carriers on the studied sites. In order to avoid unnecessary moves, the algorithm uses the concept of current carrier. The agent studies all the sites of the current carrier before moving on to the next. The algorithm also maintains a tree of carriers, where a carrier c is a child of a carrier c if c was discovered for the first time while visiting c . Carriers are treated in a depth-first-search manner for performance reasons.

Description

In addition to the upper bound B on the largest period p of the C-graph, our algorithm uses the variables described below.

The algorithm uses its own numbering to identify the sites. This way, it will work even if the C-graph is anonymous.

• currentNumber : number of the currently studied site.

If the C-graph is labeled, the agent maintains a correspondence table between the numbers given by the algorithm and the real identifiers of the sites.

• numberToID : numberToID[j] is the identifier of the site number j.

The agent maintains an ordered rooted tree whose different vertices correspond to the different encountered carriers.

• tree : the carrier tree.

• currentCarrier : identifier of the currently studied carrier.

For each carrier i present in tree, we have the following variables:

• route[i] is an array of length 3B (indexed from 0 to 3B -1); it is used to memorize the sequence of sites visited by the carrier i.

• position[i] is an integer between 0 and 3B -1 (included); it indicates the current position of the carrier i regarding to route[i].

• period[i] is an integer between 1 and B (included); it indicates the minimum period of the carrier i given the current knowledge.

Correctness

Theorem 4. Algorithm Explore-With-Wait correctly explores and maps in finite time any C-graph, even anonymous, but provided that an upper bound B on the maximum period is known.

Proof. First observe that when an agent stays at a site for 2B time units, where B is the known upper bound on the maximum period, it sees all the carriers visiting that site. Moreover, after filling in the matrix with that information, it is able to predict at any point in the future which carrier will be at that site. Since the C-graph is connected, the agent will miss no carriers and thus no sites either. At the end of the algorithm, the matrix will be completely filled in and it will be equivalent to a map of the C-graph.

Algorithm Explore-With-Wait -Our C-graph exploration algorithm 1: bFinite ← false 2: currentNumber ← 1 3: currentCarrier ← 1 4: tree ← tree reduced to a single vertex (the root) corresponding to the carrier 1 5: while (bFinite = false) do for each carrier i present on the current site at the current time do 4:

if i absent in tree then

5:

Add i as the last child of currentCarrier in tree 6:

route[i] ← array of length 3B filled with 0 7:

position[i] ← 0 8: end if 9: route[i] position[i] ← currentNumber 10:
end for 11: end for After each time unit:

1: for each carrier i present in tree do Compute from the array route[currentCarrier] the foremost journey using only currentCarrier that goes to the next site marked 0 on currentCarrier's route 3: else currentCarrier ← identifier i of the first carrier following the DFS order in tree such that the value 0 appears in route[i] 6:

Let (c i 1 , c i 2 , . . . , c i l ) be the path of carriers in tree from oldCarrier = c i 1 to currentCarrier = c i l .

7:

Compute from the arrays route[.] a foremost journey using only those carriers and such that, if the journey uses the carrier c i j and later the carrier c i j , then j ≤ j . 8: end if 9: Transform the journey so that it leaves each site at most once (by waiting on the site) 10: Follow this journey 11: currentNumber ← currentNumber + 1 12: numberToID[currentNumber] ← identifier of the current site (if applicable)

After each time step along the journey: 1: for each carrier i present in tree do Proof. The procedure findAndReachNextSite() is executed between two executions of Procedure studyCurrentSite(). This is done at most n times because a site is studied only once.

Let us first prove that the agent makes at most O(n 2 ) moves in total in the different calls to the procedure findAndReachNextSite(). From the previous remark, it is sufficient to prove that the agent performs at most n moves for each execution of Procedure findAndReachNextSite(). This is obviously the case as the path from the current site to the next unvisited site is such that it leaves each site at most once.

We now prove that the number of moves and time units is in O(kp).

Note that an agent finishes studying the sites of the current carrier's route before going on another carrier's route. Therefore, given a carrier c, the calls to procedure findAndReachNextSite() that stay on carrier c (line 2) are consecutive. Since the agent follows the foremost journey computed from the array route[currentCarrier] that only uses currentCarrier to go from the current site to the next unvisited site, the different journeys corresponding to these calls are consecutive and thus disjoint portions of c's route. Therefore the total number of moves and time units performed by the agent during these calls concerning carrier c are bounded by p.

Let us now focus on the calls to procedure findAndReachNextSite() that do not stay on the same carrier (lines 4-7). Note that the concatenation of the paths computed line 6 in these calls consists of at most a DFS traversal of the tree of carriers. Since a given carrier is at most once the end of such a path, a carrier is at most its degree plus one times in a path. Each time, at most p moves and time units are used. Hence these calls use at most 3kp moves and time units. In total, all the calls to procedure findAndReachNextSite() (whether using line 2 or lines 4-7) use at most 4kp moves and time units.

We finally prove that the number of moves and time units is in O(np). This is done by refining the previous argument. A carrier is always added as a leaf to the tree of carriers. Moreover, a carrier is used only if the agent goes to visit an unvisited site of the carrier. Since the agent has to visit at most n sites, it means that at most n carriers of the tree are used. Hence the number of moves and time units is bounded by 4np.

With the algorithm Explore-With-Wait, the agent actually moves only when executing Procedure findAndReachNextSite(). This gives the following corollary. Combining the previous results, we obtain the following corollary. Corollary 3. Given the a priori knowledge of an upper bound B = O(p) on the maximum period p, Algorithm Explore-With-Wait is asymptotically optimal in the general case with respect to both the move and the time complexities. The optimal worst-case move complexity is in Θ(min{kp, np, n 2 }) while the optimal worst-case time complexity is in Θ(np).

Specific cases

We showed in the previous section the optimal worst-case move and time complexities for the C-graph exploration problem in the general case. This section is devoted to the specific cases of homogeneous or highly-connected Cgraphs. In both cases, we prove that the worst-case move and time complexities remain the same as in the general case. Note, however, that when considering C-graphs being both homogeneous and highly-connected, we know from [START_REF] Flocchini | On the exploration of timevarying networks[END_REF] that the optimal worst-case time complexity is at most O(kp), even when n is large.

The homogeneous case

If we consider the homogeneous C-graphs (but not necessarily highlyconnected), the worst-case time and move complexities remain the same as in the general case.

Theorem 5. Given the a priori knowledge of an upper bound B = O(p) on the maximum period p, Algorithm Explore-With-Wait is asymptotically optimal in the homogeneous case with respect to both the move and the time complexities. The optimal worst-case move complexity is in Θ(min{kp, np, n 2 }) while the optimal worst-case time complexity is in Θ(np).

Proof. The result directly follows from Theorem 2, Theorem 3 and Corollary 3.

The highly-connected case

If we consider the highly-connected C-graphs (but possibly not homogeneous), the worst-case time and move complexities remain the same as in the general case. (necessary for connectedness). There exists a family G n,p,k of labeled highlyconnected C-graphs with n sites, k carriers and maximum period p such that, for any algorithm, there exists a C-graph in this family which cannot be explored by the algorithm using less than (p -1)(n -1 - G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) as the set of all the C-graphs G((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u k-1 , t k )) with, for every q ≤ i ≤ k -1, u i ∈ S i and 1 ≤ t i+1 ≤ p, if i is odd, 1 ≤ t i+1 ≤ p -1, if i is even. Claim 2. For every q, 1 ≤ q ≤ k, there exist u i and t i+1 satisfying u i ∈ S i and 1 ≤ t i+1 ≤ p (t i+1 ≤ p -1 when i is even) for every i, 1 ≤ i ≤ q -1, such that for every graph G ∈ G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) we have

T q (G) ≥ (p -1) q-1 2 i=1 |S 2i | + p q-1 2 i=1 |S 2i-1 |.
Proof of the Claim: We prove the claim by induction on q. The base case q = 1 is trivially true. Fix any q such that 1 ≤ q ≤ k -1, and assume, by induction hypothesis, that the claim holds for the value q.

Let G q be the family G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q )) whose existence is guaranteed by the induction hypothesis. Note that all C-graphs in G q have exactly the same routes R(c i ), for 1 ≤ i ≤ q. We can thus define H q to be the C-graph consisting only of the carriers c 1 to c q of any C-graph in G q . Let us consider now the agent A starting at s 1 at time 0 in H q . By induction hypothesis and by construction of H q , the agent A sees c q for the first time at time t with t ≥ (p -1)

q-1 2 i=1 |S 2i | + p q-1 2
i=1 |S 2i-1 | time units. Thus there exists u q and t q+1 satisfying u q ∈ S q and 1 ≤ t q+1 ≤ p, if q is even, 1 ≤ t q+1 ≤ p -1, if q is odd, such that A is never at u q at a time equal to t q+1 modulo the period p of c q+1 before time t + p |S q |, and thus before time (p -1)

q 2 i=1 |S 2i | + p q 2 i=1 |S 2i-1 |.
Consider now the agent A starting at s 1 at time 0 in any C-graph G in G n,p,k ((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u q-1 , t q ), (u q , t q+1 )). Before time (p-1)

q 2 i=1 |S 2i |+ p q 2
i=1 |S 2i-1 |, the agent will behave exactly the same as in H q and will not see the carrier c q+1 . This concludes the proof of the claim. ♦

The lemma follows by considering the claim for the last value q = k, and removing the assumption k ≤ n -1.

Again, summarizing the previous lemma, using Corollary 3, and considering the asymptotic behavior, we obtain the following theorem. on the maximum period p, Algorithm Explore-With-Wait is asymptotically optimal in the highly-connected case with respect to both the move and the time complexities. The optimal worst-case move complexity is in Θ(min{kp, np, n 2 }) while the optimal worst-case time complexity is in Θ(np).

Figure 1 :

 1 Figure 1: The C-graphs G 0 and G t of the family G.

Lemma 1 .

 1 For any integers n, k, p such that n ≤ p + (k -1)(p -1) (necessary for connectedness), there exists a labeled homogeneous highly-connected C-graph G n,k,p with n sites, k carriers and period p such that any algorithm needs at least min{kp -1, n 8 p -1, 7n 8 ( n 8 -1)} moves to explore it.Sketch of proof. For any feasible choice of the parameters n, k, and p, we construct a C-graph in a way that forces some sites to be visited many times in order to visit the other sites. Different constructions are used according to the relative values of the different parameters, yielding the different terms of the minimum.Proof. Fix any integers n ≥ 16, k, and p such that n ≤ p + (k -1)(p -1).

1 S 2 , 2 S 2 , 3 S 2 , 4 S 1 , 1 S 1 , 2 S 1 , 3 S 1 Figure 2 :

 122232411121312 Figure 2: The C-graph G n,k,p used in Case 1 of the proof of Lemma 1, leading to the lower bound Ω(min{kp, np}). Here n = 19, k = 2, and p = 11.

Figure 3 :

 3 Figure 3: The C-graph G n,k,p used in Case 2 of the proof of Lemma 1, leading to the lower bound Ω(n 2 ). Here n = 41, k = 2, and p = 120.

Lemma 2 .

 2 Consider any n ≥ 2, k, and p such that n ≤ p + (k -1)(p -1) (necessary for connectedness). There exists a family G n,p,k of labeled homogeneous (connected) C-graphs with n sites, k carriers and period p such that, for any algorithm, there exists a C-graph in this family which cannot be explored by the algorithm using less than p(n -1 -n-1 min(n-1,k) ) time units.Sketch of proof. The C-graphs used to prove this theorem are constructed as follows. Carriers are numbered from 1 to k. The carriers all have period p. A carrier i has only common sites with carriers i -1 and i + 1. More precisely, carrier i shares exactly one site with carrier i -1 and visits it exactly once per period. The proof is then based on the fact that the agent does not know precisely in which C-graph it is. In particular, the agent does not know when and on which site of carrier i -1 the next carrier (number i) will pass. It is possible to prove, roughly, that the agent must wait at least p time units on each site to be sure to find the next carrier, leading to the claimed bound. Proof. Fix any n ≥ 2, k, and p such that n ≤ p + (k -1)(p -1). We further assume that k ≤ n -1 (otherwise the exceeding carriers are fixed to have the same route as the first carrier). Let S = {s 1 , s 2 , . . . , s n } be the set of sites and let C = {c 1 , c 2 , . . . , c k } be the set of carriers. Let us partition S into k + 1 subsets S 0 , S 1 , . . . , S k-1 , S k such that S 0 = {s 1 }, |S k | = n-1 k , and for 1 ≤ i ≤ k -1, S i has size n-1 k or n-1 k .

14 : 1 :

 141 if no value 0 in any array route[.] then 9: Finish by providing the C-graph map (variables route[.], position[.] and eventually numberToID if the C-graph is labeled) Procedure studyCurrentSite() -collect all possible information on the current site Stay on the current site for 2B time units 2: for each time unit do 3:

2 : 3 : 4 :

 234 position[i] ← position[i] + 1 3: end for Procedure cleaning() -uses the acquired knowledge to update the variables 1: for each carrier i present in tree do 2: period[i] ← minimum period of route[i] between position[i]-2B +1 and position[i] Make the whole array route[i] periodic of period period[i], using the values of route[i] between position[i] -2B + 1 and position[i] position[i] ← position[i] mod period[i] 5: end for Procedure findAndReachNextSite() -find the next site to study and go there 1: if route[currentCarrier] still contains the value 0 then 2:

2 :

 2 position[i] ← position[i] + 1 mod period[i] 3: end for 4.3.4. Move and time complexities Lemma 3. When executing algorithm Explore-With-Wait, the agent makes at most O(min{kp, np, n 2 }) moves and uses at most O(min{kp, np}) time units in total in the different calls to procedure findAndReachNextSite().

Corollary 1 .

 1 With the algorithm Explore-With-Wait, the agent makes at most O(min{kp, np, n 2 }) moves to explore any n-site k-carrier C-graph of maximum period p.On the other hand, time is also spent when studying a site, in the calls to procedure studyCurrentSite().

Lemma 4 .Corollary 2 .

 42 When executing algorithm Explore-With-Wait, the agent uses at most O(nB) time units in total in the different calls to the procedure studyCurrentSite(), where B is a known upper bound on p.Proof. The procedure studyCurrentSite() is executed when the agent studies a site. This is done at most n times because a site is studied only once. During the study of a site, the agent stays O(B) time units on the site to note all passing carriers. This gives the bound claimed in the lemma.The obtained results from Lemma 3 and Lemma 4 give the following corollary, noticing that time is only spent in the two procedures studyCurrentSite() and findAndReachNextSite(). The algorithm Explore-With-Wait allows to explore any n-node C-graph in O(nB) time units, where B is a known upper bound on p.

Lemma 5 .

 5 Consider any n ≥ 2, k, and p such that n ≤ p + (k -1)(p -1)

Theorem 6 .

 6 Given the a priori knowledge of an upper bound B = O(p)

Table 1 :

 1 Comparison of our results (bottom of each cell, in red color) with the results obtained in

  . . . , s i l } for some l, then the route R(c i ) is the route starting at s 1 at time 0, visiting the sequences (s 1 , s 2 , . . . , s n-n/8 , s i 1 ), (s 1 , s 2 , . . . , s n-n/8 , s i 2 ), up to (s 1 , s 2 , . . . , s n-n/8 , s i l ).

 [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF]Partially supported by the ANR project DESCARTES (ANR-16-CE40-0023), and the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02).

2 Partially supported by the African Center of Excellence in Mathematics, Computer Science and ICT (CEA-MITIC)

Sketch of proof. The C-graphs used to prove this theorem are constructed as follows. Carriers are numbered from 1 to k. The carriers of odd identifier, respectively even, are of period p, respectively p -1. A carrier i has only common sites with carriers i -1 and i + 1. (The alternation of periods thus ensures high connectivity.) More precisely, carrier i shares exactly one site with carrier i -1 and visits it exactly once per period. The proof is then based on the fact that the agent does not know precisely in which C-graph it is. In particular, the agent does not know when and on which site of carrier i -1 the next carrier (number i) will pass. It is possible to prove, roughly, that the agent must wait at least p time units on each site to be sure to find the next carrier, leading to the claimed bound.

Proof. Fix any n ≥ 2, k, and p such that n ≤ p + (k -1)(p -1). We further assume that k ≤ n -1 (otherwise the exceeding carriers are fixed to have the same route as the first carrier).

Let S = {s 1 , s 2 , . . . , s n } be the set of sites and let

Fix any u 1 , u 2 , . . . , u k-1 and t 2 , t 3 , . . . , t k such that, for every 1

The C-graph G((u 1 , t 2 ), (u 2 , t 3 ), . . . , (u k-1 , t k )) is defined as follows.

Let u 0 = s 1 and t 1 = 0. Consider any i such that 1 ≤ i ≤ k. The route R(c i ) is any route going through (and only through) all the sites in S i ∪{u i-1 } satisfying the following three conditions. First, c i is of period p if i is odd, and of period p -1 if i is even. Second, c i visits u i-1 only once per period, at all times equal to t i modulo its period. Third, the route R(c i ) does not depend on the values u l and t l+1 , for l = i -1.

The family G n,p,k is defined as the set of all C-graphs G((u 1 , t 2 ), (u 2 , t 3 ), . . . ,

even. All these C-graphs are labeled highly-connected C-graphs with n sites, k carriers and maximum period p. (Indeed, note that, for every 1 ≤ i ≤ k -1, c i and c i+1 meet at u i at least every p(p -1) time units.)

Let A be any exploring agent (i.e. executing any exploration algorithm).

Given 1 ≤ i ≤ k and G a C-graph of G n,p,k , let T i (G) be the first time at which the agent A, starting at s 1 at time 0 in G, sees the carrier c i . Given q, 1 ≤ q ≤ k, and u 1 , u 2 , . . . , u q-1 and t 2 , t 3 , . . . , t q in the usual ranges, we define


domain: sdv sde

text:
This work was made possible by the active

THE SPECIFICITY OF P BAND POLINSAR DATA OVER VEGETATION

Pascale Dubois-Fernandez (1) , Sébastien Angelliaume (1) , Jean-Claude Souyris (2) , Franck Garestier (3) , Isabelle Champion (4) (1) ONERA, DEMR, Centre de Salon de Provence, BA701, 13661 Salon Air cedex, France , Email: pdubois@onera.fr [START_REF] Champion | Tree architecture determination in remote sensing analytical models : The Bray experiment[END_REF]

ABSTRACT/RESUME

A polarimetric and PolInSAR analysis has been conducted on the Nezer forest (Southern France) at L and P band on high resolution SAR data acquired with the ONERA RAMSES system in January 2004. The dataset was investigated for its potential for retrieval of forest parameters from SAR data using three different techniques:

• Radiometric inversion from the cross-polarized term, • PolInSAR inversion based on the random-volume over ground model • An approach based on the anisotropy parameter. This paper concentrates on polarimetric and PolInSAR inversion. The observed linear regression between anisotropy and vegetation height is inverted and provides a RMS error of the order of 2m. This technique displays no saturation at P band.

The PolInSAR data behaviour over the forest is consistent with the RVoG model. The standard inversion described in the literature is modified to account for the higher expected penetration at P band, by selecting a given extinction coefficient or a range of extinction coefficients. The inversion results are precise to within 1.2m. When the baseline is properly selected, the extinction coefficient is a weak parameter.

The concept of Compact Polarimetry (CP) as proposed by JC Souyris [START_REF] Jc Souyris | Compact polarimetry based on symmetry properties of geophysical media : The pi/4 mode[END_REF] is explored in the context of PolIn-SAR inversion and the accuracy of the Compact PolIn-SAR inversion is shown to be very similar to the one obtained with the full polarimetry. A preliminary assessment of the ionospheric effect on such an inversion shows low sensitivity of the inversion to Faraday effects when the one-way rotation is less than 15°. The mode where the transmit wave is circularly polarised is extremely promising..

INTRODUCTION

The Nezer forest is constituted by parcels of pine trees, which are characterised by different tree ages. It is an artificial forest managed by the French agronomic research center (INRA), providing an accurate and extensive ground truth. In this paper, we present the data set, we then propose a polarimetric inversion technique based on the anisotropy parameter, the potential of P band PolInSAR data for vegetation characterisation is presented and finally the concept of compact polarimetry is explored for PolIn-SAR applications. In an earlier paper [START_REF] Dubois-Fernandez | Ramses P band and L band campaign over the Nezer forest: calibration and polarimetric analysis[END_REF], we have presented the calibration procedure and the radiometric analysis performed at L and P bands.

THE DATASET

This site is a well monitored forest with uniform rectangular plots of pine trees. [START_REF] Champion | Tree architecture determination in remote sensing analytical models : The Bray experiment[END_REF]. A large variety of tree heights and age can be found. The forest is maintained and has little undergrowth. The topography is almost flat. In Figure 1, the amplitude image and the interferometric complex coherence (argument and amplitude) for a P band couple are shown. In the phase image, the forest plots appear significantly higher than the bare surfaces.

POLARIMETRIC INVERSION

The different polarimetric parameters as proposed by Cloude and Pottier [START_REF] Dubois-Fernandez | PolInSAR calibration of deramp-on-receive system: example with the RAMSES airborne system[END_REF] are analysed and their potential for biomass inversion is assessed. One particular parameter appeared extremely promising: the anisotropy. Note that the L-band data presents a saturation level, whereas the P band analysis shows no such behaviour with a steady decrease in anisotropy as the age or height increases.

The full inversion was performed based on the relationship obtained by fitting a straight line through the points from Figure 2 at P band [START_REF] Garestier | Polar and PolInSAR analysis of pine forest at L and P band on high resolution data[END_REF]. The inversion results are presented in Figure 3, with a RMS error in height of the order of 2m.

The anisotropy parameter is an extremely interesting lead and needs to be fully evaluated on a large range of biomes to access its true characterization potential. The studies to be conducted will have to explore the effect of slope, the effect of species and the behaviour of such an indicator for denser forest. Furthermore, the anisotropy is a parameter which is extremely sensitive to thermal noise level as it is formed by using the second and the third eigenvalues obtained with the Cloude decomposition. The usual measure of SNR (signal to noise ratio) relies on the backscatter level in one channel. An analy-sis on the forest data indicates that the third eigenvalue is often as much as 8dB below the first one. In order to provide a meaningful measure of the anisotropy, i.e., of the third eigenvalue, we conclude that the 0 σ NE over the co-pol channel must be at least 3dB below the level of the third eigenvalue, implying a SNR of at least 12dB in the co-polar channels.

POLINSAR DATASET

Before any advanced analysis, it is essential to validate the PolInSAR calibration. This is done by analysing a bare surface. tween the different polarisations. As expected, the standard deviation of the phase varies with the coherence and the number of independent samples in the window following the formula: . We primarily observe that for forests higher than 6m, the polarimetric phase centers start to be widely dispersed.

RVOG MODEL AND P BAND

In the Random Volume Over Ground model [START_REF] Cloude | An Entropy Based Classification Scheme for Land Applications of Polarimetric SAR[END_REF] the signal backscattered from the forest is modelled as the combination of a ground contribution and a volume only contribution. The ground contribution can be the surface scattering or double bounce effect linked to the tree trunks. The associated interferometric coherence is assumed to be one (no decorrelation). The interferometric coherence associated with the volume contribution is shown to be polarization independent (under the hypothesis that the attenuation is polarization independent) even though the corresponding backscattering depends on polarization [START_REF] Treuhaft | Vegetation characteristics and underlying topography form interferometric radar[END_REF]. When both contributions are present (they are assumed independent), the corresponding interferometric coherence T γ can be written as:

(

) 2
where V γ is the volume only coherence, g γ is the ground coherence and The parameter inversion is usually performed via a lookup table (LUT). In order for this scheme to be successful, one must be certain that the volume only coherence is observed for one polarisation. This can be true at X or C band but becomes more questionable as the frequency decreases. At P band, this is certainly rarely the case. On the complex unitary circle, the pseudo-ellipse will shift For the young forest (right plots) and if we assume that the RvoG model is valid, we can conclude that the volume only contribution is not observed as the extreme (or highest) phase centre (green dot) in Figure 7 is not inside the LUT (look-up table) area. In the following paragraphs, we describe how the initial procedure was modified for lower frequency acquisition.

ADAPTED INVERSION SCHEME

Straighforward approach

If the model is applicable, we know that the volume only coherence must lie on the fitted line to the left of the last observed coherence. We then assume a given attenuation coefficient; for P band we chose 0.3 dB/m from the analysis of a trihedral under canopy. The volume only contribution is determined as the intersection of the fitted line and the curve corresponding to the theoretical volume coherence associated with this attenuation coefficient (Eq 3). This position is then inverted for height.

In Figure 8, we present the corresponding inversion results. The lower vegetation plots are not inverted properly, certainly because little interaction occurs between the EM waves and the canopy at P band. The inverted height is extremely stable within a forest plot as can be seen in Figure 9 with an observed variation of the order of 1m.

Sensitivity analysis

The same approach was also followed for other attenuation coefficients ranging from 0.1 to 0.5 dB/m. The sensitivity of the inversion to the attenuation coefficient was found to be weak in our data set, certainly because for the studied baseline. In Figure 9, the inversion results for the two attenuation coefficients (0.1 and 0.5 dB/m) are provided. This low sensitivity can be explained by observing that for the study dataset, the baseline was such that in most cases the fitted line and the iso-height curve (obtained by varying the attenuation) associated with the volume only coherence are almost parallel.

COMPACT POLINSAR

The usual polarimetric SAR design architecture are built around the standard linear basis, H and V. On transmission, the radar interleaves pulses with a horizontal (H) and vertical (V) polarisation. On receive, both polarisations are received simultaneously. Full polarimetry has proved its increased potential compared to single channel acquisition. Several space-borne SAR systems in the near future will have this capability but will operate in the polarimetric mode only ponctually. This is linked to the added complexity and timing constraints in the transmit chain when two orthogonal polarisation have to be transmitted on interleaved pulses. To maintain performance, the imaged swath is usually halved, resulting in a reduced coverage. One way around that is to restrict to dual-polarised mode as done by ENVISAT or ALOS-PALSAR. These satellites can transmit only one polarisation (H or V) and receive both H and V. This solution has proven very useful but can be improved. JC Souyris in [START_REF] Jc Souyris | Compact polarimetry based on symmetry properties of geophysical media : The pi/4 mode[END_REF][START_REF] Jc Souyris | SAR Compact Polarimetry for Earth Observation and Planetology: Concepts and Challenges[END_REF] proposed an elegant alternative to the dual pol mode where instead of transmitting one of the two linear orthogonal polarised waves, the system transmits only one polarisation either H+V or circular (right or left circular, RC, LC). He called this mode compact polarimetry (CP). He showed that the polarimetric information is well preserved for natural targets for which some symmetrical properties can be assumed. For these targets, he reconstructed an equivalent to the coherence matrix very similar to the one issued from full polarimetric data (FP). K Raney [START_REF] Raney | Hybrid polarimetric SAR Architecture[END_REF][START_REF] Raney | Dual-Polarized SAR and Stokes Parameters[END_REF] followed a parallel axe of research and showed how the Compact Polarimetry Stokes parameters can provide information almost equivalent to the full polarimetry case. Other papers have also explored the same concepts [START_REF] Stacy | Compact polarimetric analysis of X band SAR data[END_REF][START_REF] Ainsworth | Analysis of Compact polarimetry Imaging Modes[END_REF]

Compact PolInSAR

We decided to test the potential of compact polarimetry on the PolInSAR inversion at P band. Several modes were tested:

Name Transmit Receive Dual-Pol 1 H H,V Dual-Pol 2 V H,V PC1(Pi/4 linear) 45° H,V PC2 (Pi/4 RC) LC H, V PC3 (Circular) LC LC, RC
The measurements on the two receiving channels are then noted in a vector form, as follows:

Dual-Pol 1: or 2) is ignored in the rest of the paper. Note first that the last two cases (PC2 and PC3) can be considered as equivalent as [START_REF] Garestier | Polar and PolInSAR analysis of pine forest at L and P band on high resolution data[END_REF] In the first part of this paper, we have shown that the volume only coherence was in general not observed in the Landes forest at P band. The inversion then consists in fitting a line through the coherences and computing the intersection of this line with the volume only coherence associated with a given attenuation. This point provides the vegetation height. The key step is therefore to produce this line. In the standard inversion with full polarimetric data, the loci of all interferometric coherences associated with the different polarisation states of the receiving and transmitting antennas is used to obtain the line. This is a 4 parameter space as the polarisation of each antenna can be parametrised with 2 parameters, the ellipticity and the orientation. In this compact polarimetry mode, the transmit polarisation is fixed resulting in a two parameter space corresponding to the polarisation state of the receiving antenna. Notice that because the reception occurs on two orthogonal polarisation, any receiving antenna polarisation can be synthesized from the data. In the compact PolInSAR inversion, we compute the loci associated with all the polarisation state of the receiving antenna (two parameter space) described as follows:

T D HV HH k ) , ( 1 = r (4) Dual-Pol 2: T D VH VV k ) , ( 2 =
where

k e k j r         = ψ ψ η ψ η sin cos ) , ( and [ ] ] 180 , 0 ∈ ψ and [ ] 180 , 0 ∈ η . ( 6
)
This two parameter space is a sub-space of the full polarimetric four parameter space. The angular sector described by this sub-space in the unitary circle is included (therefore smaller) in the 4 parameter-space described by the full polarimetric loci of interferometric coherences. The inversion procedure described in the previous sections can then be applied to the sub-space of interferometric coherence corresponding to the compact polarimetric mode. The compact PolInSAR inversion was evaluated as followed:

2 3 1 1 P P k j j k r r         - = * int int * * int ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( η
ψ η ψ η ψ η ψ η ψ η ψ η ψ γ k k k k k k ref ref ref =
• The explored angular sector on the unitary circle is compared to the angular sector associated with the full poalrimetric information • The inversion is performed based on the cloud of points associated with ) , ( η ψ γ . On our dataset and in the case of perfectly calibrated data, Compact PolInSAR performs as well as full polarimetric interferometry. Similar conclusions were found in the DP1 case. The DP2 case is not a good candidate. This results from the fact the VV and HV inferometric phase centers are very close to each other, providing a very small observable angular sector.

The results obtained on compact polarimetry are very encouraging but need to be taken one step further. At P band, propagation through the ionosphere introduces atmospheric effects (Faraday rotation, scintillation…) and up-to-now, most of the papers dealing with Faraday rotation correction stress the fact that correction cannot be performed on dual-pol data.

Effect of ionosphere

To initiate the problem, let's start by considering only the Faraday rotation effect. In the full polarimetry case, it has been modelled as [START_REF] Freeman | On the detection of Faraday Rotation in linearly polarized L-Band SAR backscatter signatures[END_REF][START_REF] Wright | Faraday rotation effects on L-Band spaceborne SAR data[END_REF]: where Ω is the one-way Faraday rotation.

        Ω Ω - Ω Ω                 Ω Ω - Ω Ω =
As an we have written below the expression for the measurement vector k associated with the compact polarimetry mode PC1 in the presence of Faraday rotation. Assuming the same ionosphere on the two acquisitions to be used in the interferometric processing, we first compute the measurement vectors associated with a given mode disturbed by the ionosphere and perform the inversion on these vectors. For the PC2 (circular case) the two interformetric coherences are independent of the ionosphere. This is why there is no effect in the inversion. The other cases indicate that up to a (uncorrected) Faraday rotation of the order of 15°, the inversion is still performing well. We now test the case where the two acquisitions are done through a different ionosphere (on two different days). This is more realistic eventhough the two acquisitions will be made at exactly the same time, which will minimize the differences.

      Ω Ω - Ω + + Ω Ω + Ω - Ω Ω + Ω - + + Ω Ω + Ω ) cos

Variation of ionopheric angle [°] RMS height error [m]

PC1 PC2 PC3 of less than 15°. After 15°, the inversion results are degrading significantly. The green curve, corresponding to the circular case should be ignored. In our current implementation, we use only the two coherence vectors (the interferometric coherences corresponding to the two measurement channels) and we did not consider the 2 parameter space described in equation ( 6). This will be modified in the future work. In this preliminary implementation because the RR and RL coherences are very close to each other in the unitary circle, the inversion is very sensitive to any small variation.

Discussion

This preliminary analysis is extremely encouraging because it shows that over this dataset:

• The compact PolInSAR inversion works as well as the full polarimetric mode. • The ionosphere has an effect but this effect can be neglected when the uncorrected Faraday rotation is less than 15° and when the differential Faraday rotation is less than 15°.

Further analysis are required • To validate these results over a wider range of forest type and underlying topography, • To develop specific ionospheric correction algorithm taking full advantage of the property of the compact polarimetry with a circular transmit wave.

When a wave is transmitted it propagates through the ionosphere while keeping its circular characteristic. The incident wave on the surface will be circular (assuming that the ionospheric effects are correctly described by the current model) whatever the ionosphere. The scattered field from the surface will therefore always correspond to the response of the surface to a circularly polarised wave. The propagation through the ionosphere will rotate the scattered field which will be received on two orthogonal antennas, meaning that for any Faraday rotation, the actual scattered field in response to a circular polarized wave is just a rotated version of the measured signal vector. This property is essential as it guaranties that the two parameter sub-space we talked about before is the same for any ionosphere, therefore will be the same for two acquisition acquired at different times. This does not hold when a linear polarised wave is transmitted. A straightforward example is the simple dual-pol case. A horizontally polarised wave is transmitted. Depending on the ionosphere, the surface can receive an H (no ionosphere) or V (a 90° Faraday rotation) polarised wave. The scattered fields will therefore be completely different and in that extreme case, PolInSAR analysis could not be performed.

One other main aspect which needs to be addressed is the calibration issue. How do we calibrate a CP system. K Raney pointed at some very interesting properties of such a system and this needs to be followed through.

[17]

CONCLUSION

We have presented a polarimetric inversion on P band data relying on the linear regression between the anisotropy parameter and the vegetation height.

We have found that Polinsar data can be successfully inverted using the Random Volume Over Ground (RvoG) model and an inversion procedure adapted to the P Band data, by assuming a known attenuation coefficient or a range of attenuation coefficients. The sensitivity to this parameter was observed to be weak given a proper baseline selection. The inversion proved to be performing very well at P band with a measured rms height error of 1.2m, therefore below the assumed ground measurement accuracy (Fig 8). The performance degrades significantly when the baseline is not adapted.

Compact PolInSAR was introduced and the first inversion results from compact PolInSAR were shown to be comparable to those associated with full polarimetry. The effect of the ionosphere was modelled and the preliminary assessment is very encouraging with a 15° range of ionosphere or differential ionosphere causing little to no degradation on the inversion. If this proved to be true for the majority of forest (including forest on sloping terrain), it could have an important impact on the design of a space-borne mission.

Figure 1 :

 1 Figure 1: P-Band PolInSAR data set with the Sigma0 image (top), the interferometric phase (middle), the interferometric coherence (bottom) coded with HH in red, HV in green and VV in blue

Figure 2 :

 2 Figure 2: Anisotropy versus stand age at L band (top)and versus height at P band (bottom).

Figure 3 :

 3 Figure 3: Ground measurements compared with Inverted forest height map from the anisotropy relation at P band

Figure 4 :

 4 Figure 4: Coherency region corresponding to a bare surface for three window size 61x61; 41x41 and 21x21 As seen in Figure 4, the shape of the coherency regions are radial indicating consistent height information be-

Figure 5 :Fig. 5 .

 55 Figure 5: Polarimetric phase centers heights for different pine parcel heights. Color coding: HH, HV, VV HH+VV, HH-VV Fig. 5. displays the different polarimetric phase center heights as a function of the forest height. The forest height is obtained from age with an allometric relation adapted to the Nezer forest only [2]. We primarily observe that for forests higher than 6m, the polarimetric phase centers start to be widely dispersed. Fig. 5. shows also that the relative positions of the polarimetric phase centers depend on the forest height and that the vertical position variations in function of the forest height appears to be continuous. This continuous vertical migration of the polarimetric phase centers during the forest growing has two origins. The first one is the height and size increase of the scattering objects (trunks, branches…) inducing a global elevation of the phase centres. This behaviour is observed for all the polarisation on Fig. 5. for the parcels lower than 15m. The second one is the creation or removal of coherent sources due to the size and geometry changes of these scattering objects. For example, it appears clearly on Fig. 5 that the double bounce phase centre (associated with HH-VV polarisation) becomes the lowest one for highest forests. Indeed, the DBH (diameter at breast height) increases when the forest becomes older. It induces an augmentation of the dihedral formed by the intersection of trunk and soil surface. Consequently, a double bounce scattering source appears at this level or becomes stronger, leading to a variation of the corresponding phase center height.

Fig. 5 .

 5 Fig.5. displays the different polarimetric phase center heights as a function of the forest height. The forest height is obtained from age with an allometric relation adapted to the Nezer forest only[START_REF] Champion | Tree architecture determination in remote sensing analytical models : The Bray experiment[END_REF]. We primarily observe that for forests higher than 6m, the polarimetric phase centers start to be widely dispersed. Fig.5. shows also that the relative positions of the polarimetric phase centers depend on the forest height and that the vertical position variations in function of the forest height appears to be continuous. This continuous vertical migration of the polarimetric phase centers during the forest growing has two origins. The first one is the height and size increase of the scattering objects (trunks, branches…) inducing a global elevation of the phase centres. This behaviour is observed for all the polarisation on Fig.5. for the parcels lower than 15m. The second one is the creation or removal of coherent sources due to the size and geometry changes of these scattering objects. For example, it appears clearly on Fig.5that the double bounce phase centre (associated with HH-VV polarisation) becomes the lowest one for highest forests. Indeed, the DBH (diameter at breast height) increases when the forest becomes older. It induces an augmentation of the dihedral formed by the intersection of trunk and soil surface. Consequently, a double bounce scattering source appears at this level or becomes stronger, leading to a variation of the corresponding phase center height.

  of the ground scattering (including the attenuation through the canopy) and the power return from the volume. The powers are depending on polarisation and the total coherence is simply the weighed average of the two coherences. The locus of the interferometric coherence when polarisation varies, is along a line segment (see figure6) between the point B (ground) and A (volume only). The inversion scheme as described by Cloude is as followed. (1) identify the line AB[START_REF] Champion | Tree architecture determination in remote sensing analytical models : The Bray experiment[END_REF] Choose between the two intersection points with the unitary circle the one associated with the ground 0

Figure 6 :

 6 Figure 6: RvoG behavior. The grey ellipse is the one corresponding to the position of the interferometric coherence as the polarization varies

  the ground point as penetration increases. Figure 7 is an illustration of what can happen at P Band when the ellipse doesn't contain point A associated with the volume only contribution.

Figure 7 :

 7 Figure 7: The complex unitary circle for two forest plots (age 48 on the left, age 11 on the right). The LUT is represented in the bottom figures and the green dot is the highest observed point.

Figure 8 :

 8 Figure 8: Inverted forest height versus ground measurements. RMS error of 1.2m (top figure), height profile (bottom figure)

Figure 9 :

 9 Figure 9: effect of the attenuation coefficient

Figure 10 :

 10 Figure 10: Angular extension of the interferometric coherences associated with PC1 et PC2 compared to the full polar case.

Figure 11 :

 11 Figure 11: Compact PolInSAR inversion results PC1 et PC 2 compared to the full polar case

Figure 12 :

 12 Figure 12: Influence of the one-way Faraday angle on the inversion from compact polarimetry with similar ionosphere on both measurements

Figure 13 :

 13 Figure 13: Influence of the one-way Faraday angle on the inversion from compact polarimetry with different ionosphere on both measurementsThe same procedure is applied, with one measurement vector not disturbed while the other is perturbed by a given Faraday rotation. In Fig13, the inversion results are showing little sensitivity to the ionosphere for a Faraday rotation difference

  CNES, DCT/SI/AR, 18 Avenue Edouard Belin, 31401 Toulouse cedex 9, France (3) CESBIO, 18 Avenue Edouard Belin, 31401 Toulouse cedex 9, France (4) INRA, Unité Ephyse, Centre de recehrche de Bordeaux BP81, 33883 Villenave d'Ornon cedex, France

support of ESA and CNES. We are thankful to Keith Raney for the constructive discussions around a barrel of beer in Frascati.


Corentin Boissy
email: corentin.boissy@math.univ-toulouse.fr

Slavyana Geninska
email: geninska@math.univ-toulouse.fr

RELATIVE SYSTOLES IN HYPERELLIPTIC TRANSLATION SURFACES

Keywords: 2010 Mathematics Subject Classification. Primary: 32G15. Secondary: 30F30 Translation surfaces, systoles, moduli spaces

In this paper we prove that the systole fonction on a connected component of area one translation surfaces admits a local maximum that is not a global maximum if and only if the connected component is not hyperelliptic.

Introduction

This paper deals with flat metric defined by Abelian differentials on compact Riemann surfaces (translation surfaces). For a translation surface, we define the relative systole Sys(S) to be the length of the shortest saddle connection of S. A sequence of area one translation surfaces (S n ) n∈N in a stratum of the moduli space of translation surfaces leaves any compact set if and only if Sys(S n ) → 0. The set of translation surfaces with short relative systole and compactification issues of strata are related to dynamics and counting problems on translation surfaces and have been widely studied in the last 30 years (see for instance [START_REF] Kerckhoff | Ergodicity of billiard flows and quadratic differentials[END_REF][START_REF] Eskin | Moduli spaces of abelian differentials: the principal boundary, counting problems, and the Siegel-Veech constants[END_REF][START_REF] Eskin | Sum of Lyapunov exponents of the Hodge bundle with respect to the Teichmüller geodesic flow[END_REF]).

Here, we are interested in the opposite problem: we study surfaces that are "far" from the boundary. In [START_REF] Boissy | Systoles in translation surfaces[END_REF], we have characterized global maxima for Sys and we have shown that each stratum of genus greater than or equal to 3 contains local but non global maxima for the function Sys. The constructed surfaces in [START_REF] Boissy | Systoles in translation surfaces[END_REF] are not in the hyperelliptic connected components.

In this paper, we prove that there are no such local maxima in hyperelliptic connected components (Theorem 3.1 in the text), while they exist in every other connected component (Theorem 4.1 in the text). This gives us the following characterization.

Theorem (Main Theorem). Let C be a connected component of a stratum of area one surfaces. The relative systole fonction on C admits a local maximum that is not a global maximum if and only if C is not hyperelliptic.

Note that our notion of relative systole is different from the "true systole" i.e. shortest closed curve that has been studied by Judge and Parlier in [START_REF] Judge | The maximum number of systoles for genus two Riemann surfaces with abelian differentials[END_REF]. In the rest of the paper, for simplicity, if not mentioned otherwise, the term "systole" will mean "relative systole".

Background

Translation surfaces.

A translation surface is a (real, compact, connected) genus g surface S with a translation atlas i.e. a triple (S, U, Σ) such that Σ (whose elements are called singularities) is a finite subset of S and U = {(U i , z i )} is an atlas of S \Σ whose transition maps are translations of C ≃ R 2 . We will require that for each s ∈ Σ, there is a neighborhood of s isometric to a Euclidean cone whose total angle is a multiple of 2π. One can show that the holomorphic structure on S \ Σ extends to S and that the holomorphic 1-form ω = dz i extends to a holomorphic 1-form on S where Σ corresponds to the zeroes of ω and maybe some marked points. We usually call ω an Abelian differential. A zero of ω of order k corresponds to a singularity of angle (k + 1)2π. By a slight abuse of notation, we authorize the order of a zero to be 0, in this case it corresponds to a regular marked point.

A saddle connection is a geodesic segment joining two singularities (possibly the same) and with no singularity in its interior. Integrating ω along the saddle connection we get a complex number. Considered as a planar vector, this complex number represents the affine holonomy vector of the saddle connection. In particular, its Euclidean length is the modulus of its holonomy vector.

For g ≥ 1, we define the moduli space of Abelian differentials H g as the moduli space of pairs (X, ω) where X is a genus g (compact, connected) Riemann surface and ω non-zero holomorphic 1-form defined on X. The term moduli space means that we identify the points (X, ω) and (X ′ , ω ′ ) if there exists an analytic isomorphism f :

X → X ′ such that f * ω ′ = ω.
One can also see a translation surface obtained from a polygon (or a finite union of polygons) whose sides come by pairs, and for each pair, the corresponding segments are parallel and of the same length. These parallel sides are glued together by translation and we assume that this identification preserves the natural orientation of the polygons. In this context, two translation surfaces are identified in the moduli space of Abelian differentials if and only if the corresponding polygons can be obtained from each other by cutting and gluing and preserving the identifications.

The moduli space of Abelian differentials is stratified by the combinatorics of the zeroes; we will denote by H(k 1 , . . . , k r ) the stratum of H g consisting of (classes of) pairs (X, ω) such that ω has exactly r zeroes, of order k 1 , . . . , k r respectively. It is well known that this space is (Hausdorff) complex analytic. We have the classical Gauss-Bonnet formula i k i = 2g -2, where g is the genus of the underlying surfaces. We often restrict to the subset H 1 (k 1 , . . . , k r ) of area one surfaces. Local coordinates for a stratum of Abelian differentials are obtained by integrating the holomorphic 1-form along a basis of the relative homology H 1 (S, Σ; Z), where Σ denotes the set of conical singularities of S.

2.2.

Connected component of strata. Here, we recall the Kontsevich-Zorich classification the connected components of the strata of Abelian differentials [START_REF] Kontsevich | Connected components of the moduli spaces of Abelian differentials with prescribed singularities[END_REF].

A translation surface (X, ω) is hyperelliptic if the underlying Riemann surface is hyperelliptic, i.e. there is an involution τ such that X/τ is the Riemann sphere. In this case ω satisfies τ * ω = -ω. A connected component of a stratum is said to be hyperelliptic if it consists only of hyperelliptic translation surfaces (note that a connected component which is not hyperelliptic might contain some hyperelliptic translation surfaces).

Let γ be a simple closed smooth curve parametrized by the arc length on a translation surface that avoids the singularities. Then t → γ ′ (t) defines a map from S 1 to S 1 . We denote by Ind(γ) the index of this map. Assume that the translation surface S has only even degree singularities S ∈ H(2k 1 , . . . , 2k r ). Let (a i , b i ) i∈{1,...,g} be a collection of simple closed curves as above and representing a symplectic basis of the homology of S. Then

g i=1 (ind(a i ) + 1)(ind(b i ) + 1) mod 2
is an invariant of connected component ans is called the parity of the spin structure (see [START_REF] Kontsevich | Connected components of the moduli spaces of Abelian differentials with prescribed singularities[END_REF] for details).

Here is a reformulation of the classification of connected component of strata by Kontsevich-Zorich (Theorem 1 and Theorem 2 of [START_REF] Kontsevich | Connected components of the moduli spaces of Abelian differentials with prescribed singularities[END_REF]).

Theorem 2.1 (Kontsevich-Zorich). Let H = H(k 1 , . . . , k r ) be a stratum of genus g ≥ 2 translation surfaces.

• The stratum H contains a hyperelliptic connected component if and only if H = H(2g -2) or H = H(g -1, g -1). In this case there is only one hyperelliptic component. In genus two, any stratum is connected (and hyperelliptic). • If there exists i such that k i is odd, or if g = 3, then there exists a unique nonhyperelliptic connected component. • If g ≥ 4 and, for all i, k i is even, then there are exactly two nonhyperelliptic connected components distinguished by the parity of the spin structure.

The following lemma is classical and will be useful in the next section.

Lemma 2.2. Let S be a translation surface in a hyperelliptic connected component and let γ be a saddle connection. Then γ and τ (γ) are homologous.

Hyperelliptic connected component

In this section, we prove the first part of the Main Theorem. The proof uses the following technical lemma. We postpone its proof to the end of the section. Lemma 3.2. Let D be a translation surface that is topologically a disk and whose boundary consists of n-saddle connections (a "n-gon") with n ≥ 4. We assume that all boundary saddle connections are of length greater than or equal to 1. Then, we can continuously deform D so that its area decreases and the boundary saddle connections of length 1 remain of length 1.

Proof of Theorem 3.1. Let S ∈ C be a translation surface that such that Sys(S) is not a global maximum. We use the same normalization as in [START_REF] Boissy | Systoles in translation surfaces[END_REF]: after rescaling the surface we assume that Sys(S) equals 1, and we will continuously deform S so that Sys(S) remains 1 and Area(S) decreases.

Let γ 1 , . . . , γ r be the set of saddle connections realizing the systole. Recall that γ 1 , . . . , γ r are sides of the Delaunay triangulation and that global maxima correspond to surfaces which Delaunay cells are only equilateral triangles (see Lemma 3.1 and Theorem 3.3 in [START_REF] Boissy | Systoles in translation surfaces[END_REF]). Let C 1 , . . . , C k be the connected components of S\∪ i γ i . Up to renumbering we can assume that C 1 is not a triangle. We consider τ (C 1 ), where τ is the hyperelliptic involution. We study the two possible cases whether τ (C 1 ) equals C 1 or not. Note that C 1 does not contain any singularity in its interior since there are at most two singularities in S and if there are two singularities P 1 , P 2 we must have τ (P 1 ) = P 2 .

Case 1. We first assume that τ (C 1 ) = C 1 . Since the hyperelliptic involution preserves ∪ i γ i , we have (up to renumbering) τ (C 1 ) = C 2 .

We observe that C 1 has only one boundary component. Indeed, suppose that there are more than one such components and consider a saddle connection η in C 1 that joins a singularity of one boundary component to a singularity of another boundary component. Then τ (η) is a curve in C 2 and must be homologous to η by Lemma 2.2. But C 1 \η is connected, and hence S\(η ∪ τ (η)) is connected, which is a contradiction. Therefore C 1 is a disk because it embeds in S/τ which is a sphere.

Since the boundary of C 1 consists of at least 4 saddle connections of length 1, by Lemma 3.2, we can continuously decrease its area while keeping the boundary saddle connections of length 1.

This continuous deformation of C 1 leads to the following area decreasing continuous deformation of S:

The component C 2 is deformed in a symmetric way as C 1 .

For each saddle connection γ in the boundary of C 1 , the components of S\(γ ∪ τ (γ)) correspond to components of the complementary of [γ] in the quotient sphere S/τ . Since [C 1 ] = [C 2 ], then C 1 , C 2 are in the same connected component of S\(γ ∪τ (γ)). We denote by D γ the other component. Note that D γ is empty if γ = τ (γ). We observe that if γ 1 , γ 2 are two distinct saddle connections in the boundary of C 1 , then D γ 1 and D γ 2 are disjoint. In particular, we can rotate all such components D γ independently in a compatible way with the deformation of C 1 , C 2 and we glue these components in the natural way. The area of each C i decreases while the area of the D γ remains constant. Therefore the total area of the surface decreases.

Case 2. Now we assume that τ (C 1 ) = C 1 . We claim that we can cut C 1 along saddle connections and obtain two discs A and B such that τ (A) = B and for each saddle connection γ in the boundary of A, either γ is of length 1, or τ (γ) = γ (equivalently, γ is also a boundary saddle connection of B).

To prove the claim, we first consider the Delaunay cells of S. Recall that the shortest geodesics (hence the boundary saddle connections of C 1 ) are sides of the Delaunay cells (see [START_REF] Boissy | Systoles in translation surfaces[END_REF], Lemma If

A k ∪ B k = C 1 , we define A = A k , B = B k .
The boundary of the disk A consists of n ≥ 3 saddle connections of lengths at least 1. If n ≥ 4, then from Lemma 3.2, it can be continuously deformed so that the area decreases and the boundary saddle connections of length 1 remain of length one. Otherwise A is a triangle but cannot be a equilateral triangle, hence it can also be deformed as above.

We deform B in a symmetric way. Note that A and B are directly glued together in C 1 along the boundary saddle connections of lengths greater than one. Therefore the possible changes of these saddle connections are not a problem. The deformation of S\C 1 is treated as in the previous case.

Proof of Lemma 3.2. The sum of the boundary angles (coming from the intersection of two consecutive boundary saddle connections) of D equals (n -2)π. Therefore D has boundary angles smaller than π. If such a boundary angle has a corresponding boundary saddle connection which is of length greater than 1, then by slightly changing its length we can decrease the area of the corresponding triangle and hence of D.

So we can assume that for each boundary angle smaller than π, the two adjacent saddle connections are of length 1. We claim that we can find two consecutive angles such that one is smaller than π and the other is smaller than 2π (note that since D is not necessarily embedded in the plane, it can have boundary angles greater than 2π). Indeed, consider the sequence of consecutive boundary angles of D. If each time an angle is smaller than π, the following one is greater than or equal to 2π, then the global sum will be greater than nπ, which is not possible. Now we consider the 3 consecutive saddle connections corresponding to these two angles, and see them as a broken line on the plane. We close this line by adding a segment t to obtain a quadrilateral Q (that can be also crossed). Without loss of generality, we can assume that t is horizontal. We have

Area(D) = Area(D 0 ) + Area alg (Q)
where D 0 is the translation surface obtained by "replacing" the broken line by t (see Figure 1). Here Area alg (Q) means that the part of Q below the segment t is counted negatively.

Claim: We can deform continuously Q without changing the lengths of its sides so that Area alg (Q) decreases.

Denote by MNP Q the quadrilateral Q and by a, b, c, d the lengths of the sides of Q with a being the length of the segment t = MN. Denote by α the oriented angle from MN to MQ, and by γ its opposite angle in Q (i.e. the angle from P Q to P N). Without loss of generality we assume that b = c = 1, d ≥ 1 and 0 < γ < π (in fact we must have γ > π/3 otherwise there would be a smallest saddle connection). We also have -π < α < π. Also, the sides NP and QM do not intersect since it would imply intersecting boundary saddle connections in D (see Figure 1).

Denote K = Area alg (Q). We compute K by adding the (algebraic) area of the triangles MNQ and NP Q. We obtain

(1) K = 1 2 (ad sin(α) + bc sin(γ)) .
The expression of the length of NQ gives the second equality:

(2)

a 2 + d 2 -2ad cos(α) = b 2 + c 2 -2bc cos(γ).
These two equations imply the Bretschneider's formula for Q:

(3) K 2 = (s -a)(s -b)(s -c)(s -d) -abcd cos( α + γ 2 ),
where s = a+b+c+d

2

. From now on, we fix a, b, c, d and study the variations of the area with respect to α, γ. Equation (2) implies that γ depends differentially on α. Hence we can write K = K(α). We need to prove that K ′ (α) = 0 or K(α) is a strict local maximum (note that α varies in an open set). We have:

(K 2 ) ′ (α) = abcd(1 + γ ′ (α)) sin( α + γ 2 ) cos( α + γ 2 ). D • M d • Q c • P b • N a D • M d • Q c • P b • N a D • M d • Q c • P b • N a Figure 1.
The disk D and the quadrilateral Q in 3 configurations.

We assume that K ′ (α) = 0, hence (K 2 ) ′ (α) = 0, hence we are in one of the following three cases:

(1) sin( α+γ 2 ) = 0. The conditions -π < α < π and 0 < γ < π imply α = -γ < 0. Hence the quadrilateral Q have self-intersections. Since the sides NP and QM do not intersect, the sides MN and P Q intersect. The condition α = -γ implies that the points M, N, P, Q are cocyclic, and since b = c = 1 we must have d < 1 which is a contradiction.

(2) cos( α+γ 2 ) = 0. Then α + γ = π, and therefore α > 0 and hence K > 0. From (2) and (3), we have a strict local maximum for K 2 and therefore for K.

(3) γ ′ (α) = -1. By differentiating (2) and using (1), we see that K = 0, hence Q has a self-intersection I = MN ∩P Q. By differentiating (1) and using (2), we obtain

K ′ (α) = 0 = 1 2 ( a 2 +d 2 2 -1), hence a 2 + d 2 = 2. Since d ≥ 1, we have a ≤ 1 ≤ d.

Nonhyperelliptic connected components

In this section, we prove the second part of the Main Theorem. The proof is a refinement of the proof of Theorem 4.7 in [START_REF] Boissy | Systoles in translation surfaces[END_REF]. We will need the following lemma, which is a refinement of Lemma 3.2 (2) in [START_REF] Boissy | Systoles in translation surfaces[END_REF]. Lemma 4.2. Let C ⊂ H(2k 1 , . . . , 2k r ) be a connected component of a stratum of abelian differentials with 2k 1 , . . . , 2k r ≥ 0. There exists a surface S ∈ C realizing the global maximum for the systole function, and such that there exists a shortest saddle connection γ joining a singularity of degree 2k 1 to itself and Ind([γ]) = 0.

Proof. We do as in the proof of Lemma 3.2 in [START_REF] Boissy | Systoles in translation surfaces[END_REF]. There exists a square tiled surface in C with singularities on each corner of the squares as in Figure 2, and we can assume that the top left horizontal segment identifies with the bottom left horizontal segment (see Figure 2). After a suitable transformation as in the figure, we obtain the required surface.

Proof of Theorem 4.1. In Theorem 4.7 in [START_REF] Boissy | Systoles in translation surfaces[END_REF] we have already constructed examples in each genus g ≥ 3 stratum. By Theorem 3.1 each such example is in a nonhyperelliptic component. So it remains to construct new examples only in strata with more than one nonhyperelliptic connected component.

From the Theorem of Kontsevich-Zorich stated in Section 2.2, there is more than one nonhyperelliptic connected component only for genus g ≥ 4 strata with only even degree singularities and in this case there In Figure 3 we give surfaces S 2,0 ∈ H(2, 0) and S 2,0,0 ∈ H(2, 0, 0) that are local but nonglobal maxima for the systole function. We consider the following construction: start from the surface S 2,0 and a surface M that is a global maximum for Sys in H(2k 1 , . . . , 2k r ). There exists a shortest saddle connection γ 1 in S 2,0 joining the two singularities. By Lemma 4.2, we can assume that there exists a shortest saddle connection γ 2 in M joining the singularity of degree 2k 1 to itself and such that Ind([γ 2 ]) = 0. We can assume that γ 1 , γ 2 are vertical and of the same length. Now we glue the two surfaces by the following classical surgery: cut the two surfaces along γ 1 and γ 2 , and glue the left side of γ 1 with the right side of γ 2 and the right side of γ 1 with the left side of γ 2 . We get a surface S in H(2k 1 + 4, 2k 2 , . . . , 2k r ) that satisfies the hypothesis of Theorem 4.1 in [START_REF] Boissy | Systoles in translation surfaces[END_REF] and hence is a local but nonglobal maximum. By Theorem 3.1, the surface S is necessarily in a nonhyperelliptic component.

1 • • • • • • • • • • • • • • • • 1 • • 1 • • • • • • • • • • • • • • • • 1 • γ •
We compute Spin(S): we choose a symplectic basis (a i , b i ) i of H 1 (M, Z) such that [γ 2 ] = a 1 . Then a simple computation gives [START_REF] Judge | The maximum number of systoles for genus two Riemann surfaces with abelian differentials[END_REF] Spin(S) = Spin(S 0,2 ) + Spin(M) + Ind(a 1 ) + 1 mod 2.

Since Ind(a 1 ) = 0, we have Spin(S) = Spin(S 0,2 ) + Spin(M) + 1 mod 2.

When i 2k i ≥ 4, we can prescribe any value of Spin(M) by choosing M in a suitable component and in this way we can obtain any possible value for Spin(S). Note that this is also true for M ∈ H(4) or M ∈ H(2, 2). Indeed, in these strata there are two components, the hyperelliptic one and the nonhyperelliptic one, and the spin structure distinguishes them (see [START_REF] Kontsevich | Connected components of the moduli spaces of Abelian differentials with prescribed singularities[END_REF], Theorem 2 and Corollary 5). By this construction, we obtain a local but non global maximum for Sys in any (nonhyperelliptic) connected component of any stratum H(2n 1 , . . . , 2n r ) for r ≥ 1, as soon as i 2n i ≥ 8 and 2n j ≥ 4 for at least one j ∈ {1, . . . , r}.

We do an analogous construction as above starting from S 2,0,0 (see Figure 3) and M ∈ H(0, 2 r ) with γ 1 ∈ S 2,0,0 joining the two marked points, and γ 2 ∈ M joining the marked point to itself. We obtain a local but nonglobal maximum in H(2 r+2 ). For r ≥ 2 we can choose the spin structure of M and thus get S in any nonhyperelliptic component of H(2 r+2 ). Note that for r = 1, we get S ∈ H(2, 2, 2) with odd spin structure.

b

• c There remain the following cases:

• d • a • c • d • b • a • b • c • d • e • a • b • c • d • e • a • S 2 ∈ H(2) S 1,1 ∈ H(1, 1)
• H(6). We do the same construction as above starting from S 2,0 and M ∈ H(2). We consider for M ∈ H(2) the surface S 2 in Figure 4. We see that 4)).

• H(4, 2). We do the same as for H(6), starting from S 2,0,0 and M = S 2 . • The even component of H(2, 2, 2). We do the same construction but starting from S 2,0,0 and M ∈ H(1, 1) the surface S 1,1 in Figure 4. We consider γ 2 = a (joining the two singularities of degree 1). By a direct computation, we see that the above construction gives a surface S ∈ H(2, 2, 2) with Spin(S) = 0 mod 2.

Theorem 3 . 1 .

 31 Let C be a hyperelliptic connected component of the moduli space of Abelian differentials. Let S ∈ C be a local maximum of the relative systole function Sys. Then S is a global maximum for Sys in C.

•

  3.1). This induces a decomposition of C 1 into Delaunay cells, and this decomposition is preserved by the involution τ because of the uniqueness of the Delaunay cell decomposition. We define a Delaunay subdivision D in the following way: for each Delaunay cell d, if τ (d) = d, then d, τ (d) ∈ D. If τ (d) = d and since d is cyclic it can be cut by a diagonal into two polygons d ′ and d ′′ = τ (d ′ ), then d ′ , d ′′ ∈ D. Now we use the following algorithm: We start from a pair d 0 , τ (d 0 ) in D and let A 0 = d 0 and B 0 = τ (d 0 ). • Suppose we have constructed the disks A k and B k such that τ (A k ) = B k and A k , B k are union of elements in D. If A k ∪B k = C 1 , there exists an element d k+1 ∈ D adjacent to A k along a saddle connection γ k (and τ (d k+1 ) ∈ D is adjacent to B k along τ (γ k )). We define A k+1 by gluing A k and d k+1 along γ k . Note that γ k is the only saddle connection in the common boundary of A k and d k+1 because otherwise S\(γ k ∪τ (γ k )) would be connected which is impossible in the hyperelliptic connected component.

  However, triangle inequalities for INP and IMQ give a + c > d + b and hence a > d, which is a contradiction.

Theorem 4 . 1 .

 41 Each nonhyperelliptic connected component of each stratum of area one surfaces with no marked points contains local maxima of the function Sys that are not global.

Figure 2 .

 2 Figure 2. A global maximum with a closed shortest saddle connection γ sastisfying Ind([γ]) = 0

Figure 3 .

 3 Figure 3. Local but nonglobal maxima in H(2, 0) and H(2, 0, 0)

Figure 4 .

 4 Figure 4. Global maxima in H(2) and H(1, 1)

  [a], [b] in this figure have different indices mod 2. Hence choosing γ 2 = a or γ 2 = b gives surfaces with different Spin structure (see Equation (