Pascal Hébrard
email: pascalhebrard@ds-fr.com

Emmanuel Humbert
email: humbert@iecn.u-nancy.fr

The geometrical quantity in damped wave equations on a square

Keywords: MSC Numbers: 35L05, 93D15 Damped wave equation, mathematical billards

The energy in a square membrane Ω subject to constant viscous damping on a subset ω ⊂ Ω decays exponentially in time as soon as ω satisfies a geometrical condition known as the "Bardos-Lebeau-Rauch" condition. The rate τ (ω) of this decay satisfies τ (ω) = 2 min(-µ(ω), g(ω)) (see Lebeau [9]). Here µ(ω) denotes the spectral abscissa of the damped wave equation operator and g(ω) is a number called the geometrical quantity of ω and defined as follows. A ray in Ω is the trajectory generated by the free motion of a mass-point in Ω subject to elastic reflections on the boundary. These reflections obey the law of geometrical optics. The geometrical quantity g(ω) is then defined as the upper limit (large time asymptotics) of the average trajectory length. We give here an algorithm to compute explicitly g(ω) when ω is a finite union of squares.

Let Ω = [0, 1] 2 be the unit square of R 2 and let ω ⊂ Ω be a subdomain of Ω. We are interested here in the problem of uniform stabilization of solutions of the following equation

          
u tt (x, t) -∆u(x, t) + 2χ ω (x)u t (x, t) = 0, x ∈

• Ω, t > 0, u(x, t) = 0, x ∈ ∂Ω, t > 0 u(., 0) = u 0 ∈ H 1 0 (Ω), u t (., 0) = u 1 ∈ L 2 (Ω), (0.1) where χ ω is the characteristical function of the subset ω. This equation has its origin in a physical problem. Consider a square membrane Ω. We study here the behaviour of a wave in Ω. Let u(x, t) be the vertical position of x ∈ Ω at time t > 0. We assume that we apply on ω a force proportional to the speed of the membrane at x. Then, u satisfies equation (0.1). To get more information on this subject, one can refer to [START_REF] Hébrard | Étude de la géométrie optimale des zones de contrôle dans des problèmes de stabilisation[END_REF], [START_REF] Rauch | Decay of solutions to nondissipative hyperbolic systems on compact manifolds[END_REF], [START_REF] Bardos | Sharp sufficient conditions for the observation, control and stabilization of waves from the boundary[END_REF]. With regard to the one-dimensional case, the reader can consult [START_REF] Cox | The rate at which energy decays in a damping string[END_REF] and [START_REF] Benaddi | Energy decay rate of wave equations with infinite damping[END_REF].

We do not deal here with the existence of solutions. We assume that there exists a solution u. Let us define the energy of u at time t by

E(t) = Ω |∇u| 2 + u 2 t dx.
It is well known that, for any t ≥ 0,

E(t) ≤ CE(0)e -2τ t , (0.2)
where C, τ ≥ 0. As proven by E. Zuazua [START_REF] Zuazua | Exponential decay for the semilinear wave equation with localized damping[END_REF], this result remains true in the semilinear case when the dissipation is in a neighborhood of a subset of the boundary satisfying the multiplier condition.

Let us now define Definition 0.1 The exponential rate of decay τ (ω) is defined by τ (ω) = sup{τ ≥ 0 s.t. ∃C > 0 for which (0.2) holds }.

Many articles have been devoted to finding bounds for τ (ω). The reader can consult [START_REF] Asch | The spectrum of the damped wave operator for a bounded domain in R 2[END_REF], [START_REF] Lebeau | Équation des ondes amorties[END_REF] and [START_REF] Sjostrand | Asymptotic distribution of eigenfrequencies for damped wave equations[END_REF]. In the case of a non-constant damping, the reader may see [START_REF] Cox | Achieving arbitrarily large decay in the damped wave equation[END_REF]. G. Lebeau proved in [START_REF] Lebeau | Équation des ondes amorties[END_REF] that τ (ω) = 2 min(-µ(ω), g(ω)).

Here µ(ω) denotes the spectral abscissa of the damped wave equation operator and g(ω) is a number called the geometrical quantity of ω and defined as follows. A ray in Ω is the trajectory generated by the free motion of a mass-point in Ω subject to elastic reflections in the boundary. These reflections obey the law of geometrical optics: the angle of incidence equals the angle of reflection. If a ray meets a corner of Ω, the reflection will be the limit of the reflection of the rays which go to this corner. It is easy to verify that the ray runs along the same trajectory before and after the reflection but in an opposite direction. Let γ : R + → Ω be the parametrization of the ray by arclength. Let C = rays in Ω .

Furthermore, let ρ 0 = (X 0 , α), where X 0 ∈ Ω and α ∈ [0, 2π[. Consider the ray γ ρ0 which starts at X 0 in the direction of the vector (cos(α), sin(α)). Each ray of C can be defined in this way. More precisely, if Γ = Ω × [0, 2π[ then C = {γ ρ0 s.t. ρ 0 ∈ Γ}.

In the whole paper γ ∈ C will be noted γ = [X 0 , α]. If γ ∈ C and if t > 0 is a positive real number, we write:

γ t = γ /[0,t] . Let C ′ = t>0 γ t γ ∈ C
be the set of paths of finite length not necessarily closed. For γ t ∈ C ′ of length t > 0, we define:

m(γ t ) = 1 t t 0 X ω (γ t (s))ds.
The definition of m can be extended to C. Indeed, if γ ∈ C, set m(γ) = lim sup t→+∞ m(γ t ).

It is proven in Section 1.2 that m(γ) = lim t→+∞ m(γ t ). (0.3)

For a ray γ belonging to C, m(γ) represents the average time that γ spends in Ω.

Definition 0.2 The geometrical quantity g(ω) is defined by

g(ω) = lim sup t→+∞ inf γ∈C m(γ t ).
We are interested here in a precise study of the geometrical quantity g. The first part of this paper is devoted to studying the rays. We recall some well known properties of rays. In the second part, another expression for g is given. Namely, we prove that if ω ⊂ Ω whose boundary is a finite union of C 1 -curves, then

g(ω) = inf γ∈C lim sup t→+∞ m(γ t ) = inf γ∈C m(γ).
It is easier to work with this second definition of g(ω). An important application of this theorem is given in the third part: we obtain an algorithm which gives an exact computation of g(ω) when ω is a finite union of squares. This work has many interests. At first, Theorem 2.1 gives another definition for g(ω), much more easy to manipulate than the original one. Secondly, maximizing the exponential rate of decay is interesting from the point of view of physics. For these questions, knowing exactly g(ω) is important. We give some exact computations of g(ω) with the help of our algorithm at the end of the paper. An interesting question is then: how can we choose the subset ω such that g(ω) is maximum? At the moment, this problem is still open. The following inequality is always true g(ω) ≤ |ω| (see Section 2) where |ω| is the area of ω. Let us set for α ∈ [0, 1]

S(α) = sup |ω|=α g(ω).
Some questions then arise naturally -What is the value of S(α)? In particular, is it true that S(α) = α? -Can we find a subset ω for which g(ω) = |ω|? -Can we find an optimal ω (i.e. an ω that maximizes g) among the domains that satisfy the multiplier condition? If |ω| = 0 or |ω| = 1, the answers are obvious. However, if |ω| ∈]0, 1[, these questions seem to be much more difficult and are still open.

1 Basic properties of rays

Different representations of rays

In this section, we regard billards in Ω from different point of views (see for example [START_REF] Tabachnikov | Billiards Mathématiques, SMF collection Panoramas et synthèses[END_REF]). Instead of reflecting the trajectory with respect to a side of Ω, one can reflect Ω with respect to this side. We then obtain a square grid and the initial trajectory is straightened to a line. This gives a correspondance between billard trajectories in Ω and straight lines in the plane equipped with a square grid. Two lines in the plane correspond to the same billard trajectory if they differ by a translation through a vector of the lattice 2Z + 2Z. The factor 2 in 2Z + 2Z is important. Indeed, two adjacent squares have an opposite orientation in the sense that they are symmetric with respect to their common side.

X 0 ω 1'=1 2' 3' 4' 0 1 2 1 Figure 1: Point of view of infinite plane Now, consider T = [0, 2]
2 and identify its opposite sides. A trajectory then becomes a geodesic line in the flat torus. -the point of view of geodesic lines in a flat torus T . Note that the set ω must be reflected in the same way as we did for Ω. This means that the sets ω contained in two adjacent squares must be symmetric with respect to their common side (see Figures 1 and2).

Let t > 0 and γ ∈ C. The value

1 t t 0 X ω (γ t (s))ds
does not depend on the point of view we adopt.

Open and closed rays

A ray is said to be closed if it is periodic in the flat torus. More precisely, let α be such that

tan α ∈ R -Q then ∀ǫ > 0, ∃t 0 | t ≥ t 0 , ∀X 0 ∈ Ω : if γ ρ0 = [X 0 , α] then |m(γ t ) -|ω|| < ǫ.
In other words, t 0 is independent of X 0 .

Here, |ω| stands for the area of ω. Consider now closed rays. They satisfy the following properties:

Proposition 1.2 Let γ = [X 0 , α] be a closed ray. Then, there exist p, q ∈ Z relatively prime such that: cos α = p p 2 + q 2 and sin α = q

p 2 + q 2 .
The period L of the trajectory is L = 2 p 2 + q 2 . We have Closed rays can easily be described. Let us adopt the point of view of a flat torus. Let us consider a ray γ = [X 0 , α] with X 0 ∈ T and cos α = p/ p 2 + q 2 , sin α = q/ p 2 + q 2 , p and q relatively prime. We assume that p ≥ 0 and q ≥ 0 (i.e α ∈ [0, π/2]). From remark 3.1 below, the study can be restricted to such rays.

m(γ t ) ----→ t→+∞ 1 L L 0 χ ω (γ(s))ds.
Theorem 1.1 The ray γ is an union of p + q parallel segments directed by u = cos α i + sin α j. Among these segments, p of them start at A k , 1 ≤ k ≤ p, and the q others start at

B k , 1 ≤ k ≤ q with A k 0, y 0 + q/p(2k -x 0 ) -2E( 1 2 (y 0 + q/p(2k -x 0 ))
and

B k x 0 + p/q(2k -y 0 ) -2E( 1 2 (x 0 + p/q(2k -y 0 )) , 0 ).
In addition, the distance between two neighbouring segments is constant and equal to δ = 4/L, where L = 2 p 2 + q 2 is the period.

X 0 X 1 ∆ x = 2p ∆ y = 2q A 1 A 2 A 3 B 1 B 2 Ω 0 2 4 6 8 2 4 6
Figure 3: Closed ray for p = 3 and q = 2 in the infinite plane Proof : In the infinite plane R 2 , the ray is defined by x(t) = x 0 + 2tp/L and y(t) = y 0 + 2tq/L, where L = 2 p 2 + q 2 is the period. Let us restrict the study to the segment [X 0 X 1 ] of length L. In ]X 0 X 1 [, the ray intersects p vertical straight lines defined by the equations x = 2k, k = 1, • • • , p and q horizontal straight lines defined by the equation y = 2k, k = 1, • • • , q. This gives p + q segments starting at points with coordinates 0, y 0 + q/p(2kx 0 ) and x 0 + p/q(2ky 0 ), 0 . Coming back to the point of view of the torus, this gives p + q segments starting at A k and B k . Since p and q are relatively prime, it is well known that {kq

[p], 1 ≤ k ≤ p} = {0, 1, . . . , p -1}.
Hence, if A k1 and A k2 are two neighbouring points, A k1 A k2 = 2/p. As a consequence, the distance between the straight lines (A k1 , u) and (A k2 , u) is

δ = -----→ A k1 A k2 . u ⊥ = 2 p j. -q i + p j p 2 + q 2 = 4 L .
In the same way, if B k1 and B k2 are two neighbouring points B k1 B k2 = 2/q, the distance between (B k1 , u) and (B k2 , u) is

δ = -----→ B k1 B k2 . u ⊥ = 2 q i. q i -p j p 2 + q 2 = 4 L . Let k 1 , k 2 be such that dist(A k1 , 0) = min k dist(A k , 0) and dist(B k2 , 0) = min k dist(B k , 0).
It remains to prove that the distance between the two segments starting at A k1 and B k2 is δ = 4/L. Since the distance between two points A k is 2/p, there exists n ∈ N such that the ordinate y * of

A k1 satisfies 2n ≤ y 0 + q/p(2k 1 -x 0 ) -2E( 1 2 (y 0 + q/p(2k 1 -x 0 )) < 2n + 2/p =⇒ y * = y 0 + q/p(2k 1 -x 0 ) -2E( 1 2 (y 0 + q/p(2k 1 -x 0 )) -2n < 2/p.
In the same way, there exists m ∈ N such that the abscissa

x * of B k2 satisfies 2m ≤ x 0 + p/q(2k 2 -y 0 ) -2E( 1 2 (x 0 + p/q(2k 2 -y 0 )) < 2m + 2/q =⇒ x * = x 0 + p/q(2k 2 -y 0 ) -2E( 1 2 (x 0 + p/q(2k 2 -y 0 )) -2m < 2/q.
The distance δ between the two segments verifies:

δ = -----→ A k1 B k2 . u ⊥ = |qx * + py * | p 2 + q 2 .
An easy computation shows that |qx * + py * | is an even integer number. Consequently, δ can be written as 4k/L, where k is an integer. Since 0 ≤ x * < 2/q and 0 ≤ y * < 2/p, we get δ < 8/L, and hence, δ = 4/L.

Remark 1.2 If a quarrable domain ω is such that g(ω) = |ω| then for all α ∈ [0, π/2] and for almost all X 0 ∈ T , m(γ) = |ω|, where γ = [X 0 , α]. Indeed, consider an open ray γ. Then m(γ) = |ω|. Let X 0 ∈ Ω. Assume that a ray γ starting at X 0 is closed of length L. Let M and N be two points of γ such that --→ M N is orthogonal to u and M N = δ. Let also P (s) = sM + (1 -s)N and γ s = [P (s), α], then g(ω) ≤ inf s∈[0,1] m(γ s L ) ≤ 1 0 m(γ s L )ds ≤ |ω|. If g(ω) = |ω|, then m(γ s L ) = |ω| almost everywhere. If ∂ω is a finite union of curves of class C 1 , then the number of discontinuity points of m(γ s L ) is finite.
It is null if ∂ω does not possess any segments. The remark above immediately follows.

2 An equivalent definition for g

2.1

The geometrical quantity g ′

We define, for any set ω:

Definition 2.1 The geometrical quantity g ′ (ω) is defined by

g ′ (ω) = inf γ∈C m(γ).
As easily seen, g ′ is easier to study than g. As shown in Section 3, g ′ (ω) can be computed explicitly for a certain class of domains ω. Together with Theorem 2.1, this gives an algorithm for computing g(ω).

Theorem 2.1 Let ω be a closed set whose boundary is a finite union of curves of class C 1 . Then

g(ω) = g ′ (ω).
As a first remark, the same argument as in the proof of Proposition 1.3 shows that

0 ≤ g ′ (ω) ≤ |ω|. (2.1)
The proof of Theorem 2.1 is given in the appendix. It is easy to see that g(ω) ≤ g ′ (ω). Inequality g ′ (ω) ≤ g(ω) is much more difficult to obtain. To prove Theorem 2.1, we consider a sequence of rays γ n = [x n , θ n ] and a sequence of real numbers t n → +∞ for which m(γ n tn ) → g(ω). After choosing a subsequence, there exists (x, θ) ∈ Ω × [0, 2π[ such that lim n x n = x and lim n θ n = θ.

We will now show that lim n m(γ n tn )m([x, θ] tn ) = 0. The conclusion then follows. The difficulty in this proof is that the function (x, θ) → m([x, θ] t ) is not continuous. A direct consequence of Theorem 2.1 is that it suffices to consider closed rays in the explicit computation of g(ω). Namely, let C c be the set of closed rays, then we have:

g(ω) = inf γ∈Cc m(γ).
(2.2)

Explicit computation of g

We prove in this section that for a particular class of domains ω, the properties of the geometrical quantity g we obtain above allow to compute explicitly g(ω). Let N ∈ N * , and let ω ⊂ Ω be a finite union of squares (C i,j ) 1≤i,j≤N , with

C i,j = i -1 N , i N × j -1 N , j N .
Obviously, ω is Riemann-measurable, closed and its boundary is a finite union of C 1 curves.

Influence of α

The first result we obtain is the following Theorem 3.1 Let γ = [X 0 , α] be a closed ray such that tan α = q/p, with p and q relatively prime and p + q > 2N , then

| m(γ) -|ω| | ≤ N 2 pq min{|ω|, 1 -|ω|} ≤ N 2 2pq .
Proof : We adopt the point of view of flat torus T = [0, 2] 2 . At first, let K be one of the C i,j i.e.

K = C i0,j0 = i 0 -1 N , i 0 N × j 0 -1 N , j 0 N = ABCD.
The period of γ is L = 2 p 2 + q 2 . Let δ = 4/L. Then cos α = pδ/2 and sin α = qδ/2. By Theorem 1.1, the ray γ is constituted by p + q segments directed by u. The distance between two neighbouring segments is δ.

Let us define the orthonormal frame R u = (X, 5).

-→ I u , -→ J u ), where X is such that --→ XD. u = 0, --→ XD. --→ XA = 0, -→ I u = --→ XD/|| --→ XD||, and -→ J u = --→ XA/|| --→ XA|| = u (see Figure
In this frame, the coordinates of A, B, C and D satisfy

A (0, sin α N ); B ( sin α N , sin α + cos α N ); C ( sin α + cos α N , cos α N ); D ( cos α N , 0).
The ray γ is constituted of p + q vertical segments. R of them meet K (see Figure 6). We note x 0 , x 1 , . . . x R-1 their abscissa Let

x 0 = r ∈ [0, δ] x i = x 0 + iδ, 0 ≤ i ≤ R -1 . A B C D X 0 1 2 1 2
f 1 (x) = cot α x + sin α N = cot α (x - sin α N ) + sin α + cos α N line (AB) f 2 (x) = -tan α (x - sin α N ) + sin α + cos α N = -tan α (x - sin α + cos α N ) + cos α N line (BC) g 1 (x) = -tan α x + sin α N = -tan α (x - cos α N ) line (AD) g 2 (x) = cot α (x - cos α N ) = cot α (x - sin α + cos α N ) + cos α N line (CD).
and

f (x) =            sin α N if x ≤ 0 f 1 (x) if 0 ≤ x ≤ sin α N f 2 (x) if sin α N ≤ x ≤ sin α+cos α N cos α N if x ≥ sin α+cos α N and g(x) =            cos α N if x ≤ 0 g 1 (x) if 0 ≤ x ≤ cos α N g 2 (x) if cos α N ≤ x ≤ sin α+cos α N cos α N if x ≥ sin α+cos α N . Then R f -g = sin α+cos α N 0 (f (x) -g(x))dx = |K| = 1 N 2 and 1 L L 0 χ K (γ(s))ds = δ 4 R-1 i=0 f (x i ) -g(x i ).
Let k be the number of vertical segments which meet [AB], i.e. the k segments such that

r + (k -1)δ ≤ sin α N ≤ r + kδ. 10 A B C D X x 0 x 1 x 2 Figure 6: Vertical segments in the square ABCD If 1 ≤ k ≤ R -1,
L R-1 i=0 f (x i ) = δ 4 k-1 i=0 f 1 (x i ) + δ 4 R-1 i=k f 2 (x i ) = 1 4 k-1 i=0 xi+δ/2 xi-δ/2 f 1 (x)dx + 1 4 R-1 i=k xi+δ/2 xi-δ/2 f 2 (x)dx = 1 4 r+(k-1/2)δ r-δ/2 f 1 (x)dx + 1 4 r+(R-1/2)δ r+(k-1/2)δ f 2 (x)dx. ( 3
L R-1 i=0 f (x i ) = 1 4 (p+q)δ/2N 0 f (x)dx - 1 4 r-δ/2 0 f 1 (x)dx + 1 4 r+(k-1/2)δ qδ/2N (f 1 (x) -f 2 (x))dx + 1 4 r+(R-1/2)δ (p+q)δ/2N f 2 (x)dx.
In the same way, let l be the number of segments which meet [AD]

r + (l -1)δ ≤ cos α N ≤ r + lδ.
We obtain that, in all cases

1 L R-1 i=0 g(x i ) = 1 4 r+(l-1/2)δ r-δ/2 g 1 (x)dx + 1 4 r+(R-1/2)δ r+(l-1/2)δ g 2 (x)dx = 1 4 (p+q)δ/2N 0 g(x)dx - 1 4 r-δ/2 0 g 1 (x)dx + 1 4
r+(l-1/2)δ pδ/2N (g 1 (x) -g 2 (x))dx + 1 4 r+(R-1/2)δ (p+q)δ/2N g 2 (x)dx. Finally 1 L L 0 χ K (γ(s))ds - 1 4N 2 = - 1 4 r-δ/2 0 f 1 -g 1 + 1 4 r+(k-1/2)δ qδ/2N f 1 -f 2 + 1 4
r+(l-1/2)δ pδ/2N g 1 -g 2 + 1 4 r+(R-1/2)δ (p+q)δ/2N f 2 -g 2 = tan α + cot α 8 -(r -δ/2) 2 + (r + (k -1/2)δ -qδ/2N ) 2 +(r + (l -1/2)δ -pδ/2N ) 2 -(r + (R -1/2)δ -(p + q)δ/2N ) 2 .
However, in this last equality, each of the four square terms is less than δ/2 and tan α

+ cot α = 1 sin α cos α = 4 pqδ 2 = L 2 4pq hence 1 L L 0 χ K (γ(s))ds - 1 4N 2 ≤ 1 4pq . (3.2)
We now consider:

ω T = (i,j)∈E C i,j ,
where E is a subset of {1, 2, . . . , 2N } 2 and card(E

) = N 2 |ω T | = 4N 2 |ω| ; then m(γ) = 1 L L 0 χ ωT (γ(s))ds = (i,j)∈E 1 L L 0 χ Ci,j (γ(s))ds.
Hence

m(γ) -|ω| = (i,j)∈E 1 L L 0 χ Ci,j (γ(s))ds - 1 4N 2 .

This leads to

| m(γ) -|ω| | ≤ card(E) 4pq = N 2 pq |ω|.
If the area of ω is greater than 1/2, let ω ′ be the adherence of Ωω which is also a finite union of squares C i,j , Hence

1 L L 0 χ ω ′ (γ(s))ds -(1 -|ω|) ≤ N 2 pq (1 -|ω|) or 1 L L 0 χ ω ′ (γ(s))ds = 1 - 1 L L 0 χ ω (γ(s))ds. Finally, we get | m(γ) -|ω| | ≤ N 2 pq (1 -|ω|).

Representation of ω

For convenience, consider the frame (O, I, J) with I = i/(2N ) and J = j/(2N ). As a consequence, Ω is now the square [0, N ] 2 , and T is the torus [0, 2N ] 2 . The length of closed rays defined by (p, q) (p, q relatively prime) such that cos α = p/ p 2 + q 2 and sin α = q/ p 2 + q 2 must be modified.

The period is now

L = 2N p 2 + q 2
and C i,j is such that:

C i,j = [i -1, i] × [j -1, j].
Let us define the matrix M N × N such that M i,j = 1 if C j,i ⊂ ω, and M i,j = 0 if C j,i ⊂ ω. With this notation, the matrix M is a representation of ω. As an example, if ω is as in Figure 7 then

M =         1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0         . 0 1 C 1 2 C 2 3 C
2N matrix A such that A i,j = 1 if C j,i ⊂ ω T , A i,j = 0 if C j,i ⊂ ω T , i.e. M i,j = A i,j = A 2N +1-i,j = A i,2N +1-j = A 2N +1-i,2N +1-j . (3.3)
Proof : Let B = (x 0 , y 0 ) be a point of T such that the ray γ = [B, α] does not meet a point with integer coordinates. Let us adopt the point of view of infinite plane and let B 0 , B 1 , B 2 , . . . be the intersection points of γ with the lattice Z + Z. A direct consequence of Theorem 1.1 is that B 0 B 2N (p+q) = L = 2N p 2 + q 2 . u = (p i + q j)/ p 2 + q 2 is the direction of the ray. Let n = (-q i + p j)/ p 2 + q 2 be such that ( u, n) is a direct orthonormal frame. For a point P = (k, l) with integer coordinates, let us compute the algebraic distance to the ray γ

d(P, γ) = --→ BP . n = pl -qk -(py 0 -qx 0 ) p 2 + q 2 .
There exists a point A with integer coordinates and which verifies: Let us note C i the intersection of the line meeting C and directed by u and the line belonging to the lattice Z + Z which contains B i (see Figure 9).

d(A, γ) =

There are three oblique rays of angle α γ

A = [A 0 , α], γ B = [B, α] = [B 0 , α] and γ C = [C 0 , α].
According to the definitions of A and C, the segments

[A i A i+1 ], [B i B i+1 ] and [C i C i+1 ] belong to the same square C k,l . We define ε k = 1 if [B k B k+1 ] ⊂ ω T , ε k = 0 if [B k B k+1 ] ⊂ ω T . Then, if m(γ B ) = 1 L [B0B 2N (p+q) ] χ ωT = 1 L 2N (p+q) k=1 ε k B k-1 B k ,
we have:

m(γ A ) = 1 L 2N (p+q) k=1 ε k A k-1 A k and m(γ C ) = 1 L 2N (p+q) k=1 ε k C k-1 C k .
These three rays are parallel. Hence, there exists t ∈ (0, 1) such that for all i, B i is the barycenter of (A i , t) and (C i , 1t). If the quadrilateral A i A i+1 C i C i+1 is a trapezium (or in the degenerate case a rectangular triangle), Thales' theorem implies that

B i B i+1 = t A i A i+1 + (1 -t) C i C i+1 .
If the quadrilateral is a parallelogram, this inequality remains valid because the three lengths are equal. As a consequence, we have

m(γ B ) = tm(γ A ) + (1 -t)m(γ C ).
The minimum of the three quantities m(γ A ), m(γ B ) and m(γ C ) is attained for one of the two rays γ A ou γ C . This shows that γ cannot be the minimum in the set of oblique closed rays.

It remains to find the angles α we need to consider among the rays which meet a point with integer coordinates. In the flat torus T = [0, 2N ] 2 , there are 4N 2 possible starting points. However, the ray γ = [(x 0 , y 0 ), α] with (x 0 , y 0 ) ∈ N 2 meets 2N points with integer coordinates. Indeed, γ meets the point (x 1 , y 1 ) if and only if there exists λ ∈ [0, 2N ) such that

x 1 = x 0 + λp [2] y 1 = y 0 + λq [2] .
Therefore, the points belonging to γ and with integer coordinates are exactly the 2N points obtained for λ = 0, 1, . . . , 2N -1. There exist at least 2N rays which meet a point with integer coordinates.

Proposition 3.2 Let d be the G.C.D. of p and 2N , let d ′ be such that d d ′ = 2N . Then, the 2N rays of angle α starting at (i, j) with 0 ≤ i ≤ d -1 and 0 ≤ j ≤ d ′ -1 meet one and only one time all the points of T with integer coordinates.

Proof : Let p ′ be such that d p ′ = p. We note that p ′ and d ′ are relatively prime. Let also γ 1 and γ 2 be the rays starting respectively at A and B with integer coordinates (k 1 , k 2 ) and (k

3 , k 4 ) (with 0 ≤ k 1 , k 3 ≤ d -1 and 0 ≤ k 2 , k 4 ≤ d ′ -1 )
. There exists a point C ∈ γ 1 ∩ γ 2 with integer coordinates if and only if there exist four integer numbers λ, µ, n and m such that

x = k 1 + λp = k 3 + µp + 2N n y = k 2 + λq = k 4 + µq + 2N m . Therefore, k 1 -k 3 = (µ -λ)p + 2N n and k 1 -k 3 is divisible by d. Since -(d -1) ≤ k 1 -k 3 ≤ d -1, we have k 1 = k 3 and (µ -λ)p = -2N n.
As a consequence, (µλ)p ′ = -d ′ n and since p ′ and d ′ are relatively prime, (µλ) = kd ′ , where k ∈ Z. In the same way,

k 2 -k 4 = (µ -λ)q + 2N m = kd ′ q + 2N m. Hence k 2 -k 4 is divisible by d ′ . Since -(d ′ -1) ≤ k 2 -k 4 ≤ d ′ -1, we have k 2 = k 4 and γ 1 = γ 2 .

The algorithm

In this section, we give a method to compute explicitly g when ω is a finite union of squares C i,j . At first, according to Propositions 1.1 and 3.1, the study can be restricted to closed rays starting at a point with integer coordinates. The user of the program must input the matrix M which represents ω and the value of a parameter P Qmax which avoids infinite loops (this problem never appeared until now).

The algorithm is the following 1. Compute the minimum g of the 2N numbers

1 N N i=1 M i,j and 1 N N j=1 M i,j ,
which corresponds to the minimum of m(γ) when γ is a vertical or horizontal ray.

2. From the matrix M , build the matrix A defined in (3.3).

3. For all (p, q) such that p ≥ 1, q ≥ 1, p + q ≤ 2N and p and q relatively prime, compute the number (the way to compute m p,q is explained below)

m p,q = min X∈{1,2,...,2N } 2 {m(γ)|γ = [X, arctan q/p]}. (3.4)
Then g ← min{g, m p,q }.

4. If at this step g = |ω|, the user inputs the parameter P Qmax which corresponds to the greatest product pq which will be considered ; in the other cases P Qmax = E( N 2 |ω|-g min{|ω|, 1 -|ω|}) + 1.

5. Find all the (p, q) relatively prime such that p ≥ 1, q ≥ 1, p + q > 2N , pq ≤ P Qmax. Sort these couples from the lowest product pq to the greatest one. This gives a list L containing n couples.

6. i ← 1 and as long as |ω|g ≥ N 2 pq min{|ω|, 1 -|ω|} and i ≤ n, g ← min{g, m p,q } and i ← i + 1, where (p, q) is the i-th couple of L and m p,q is defined above (see (3.4)).

Finally

• if at the end of this loop, g = |ω|, then |ω| -

N 2 P Qmax min{|ω|, 1 -|ω|} ≤ g(ω) ≤ |ω|.
This means that one of the following cases occurs; g(ω) = |ω|, or too few families of rays have been considered.

• if g = |ω|, according to Theorem 3.1, g(ω) is equal to g.

We now present the method of computation defined in (3.4) for two relatively prime integers p ≥ 1, q ≥ 1. At first, let us consider the ray γ 0 = [0, arctan q/p] and let us study the way to compute m(γ 0 ). Its period is L = 2N p 2 + q 2 and between the instants t = 0 and t = L, it meets 2N (p + q -1) + 1 points which have at least one integer coordinate. Let P 1 ,..., P 2N (p+q-1)+1 be these points (see Figure 10). Remember that P l(p+q-1)+1 , 1 ≤ l ≤ 2N have integer coordinates. Let (i k ), (j k ) and (ε k ) be the three other finite sequences (1 ≤ k ≤ 2N (p + q -1)) defined by

P k P k+1 ⊂ [i k , i k + 1] × [j k , j k + 1]
and

ε k = 1 if [i k , i k + 1] × [j k , j k + 1] ⊂ ω 0 if not .
Then, m(γ 0 ) = 1 L 2N (p+q-1) k=1

ε k P k P k+1 , the computation of m(γ 0 ) is equivalent to the computation of the sequences (P k P k+1 ), (i k ) and (j k ).

• Computation of the lengths P k P k+1 At first, note that it suffices to compute the lengths P k P k+1 for 1 ≤ k ≤ p + q -1. Indeed, ---------→ P k+(p+q-1) P k = p i + q j, hence the sequence (P k P k+1 ) is periodic of period p + q -1. Since p and q are relatively prime, P 1 and P p+q-1 do not have integer coordinates.

Then, the equations of the ray γ 0 are x = pt/ p 2 + q 2 and y = qt/ p 2 + q 2 . It meets the vertical lines defined by x = i at instants t i = i p 2 + q 2 /p at points (i, iq/p) and the horizontal lines defined by y = j at instants t ′ j = j p 2 + q 2 /q and at points (jp/q, j).

Let us then define the list

V 1 by V 1 = {t ′ j , 1 ≤ j ≤ q -1} ∪ {t i , 1 ≤ i ≤ p -1}.
Let V 2 be the list obtained from V 1 by sorting its elements in increasing order. Let also σ be the permutation of {1, 2, . . . , p + q -2} such that

V 2 = σ(V 1 ) = {V 1 σ(1) , V 1 σ(2) , . . . , V 1 σ(p+q-2) }.
Let V 3 and V 4 be defined by

V 3 = {0} ∪ V 2 ∪ { p 2 + q 2 } and V 4 = {V 3 2 -V 3 1 , V 3 3 -V 3 2 , . . . , V 3 p+q -V 3 p+q-1 }.
Finally, let V be defined by

V = V 4 ∪ V 4 ∪ • • • ∪ V 4 2N times , then for all k, 1 ≤ k ≤ 2N (p + q -1) P k P k+1 = V k and m(γ 0 ) = 1 2N p 2 + q 2 2N (p+q-1) k=1 ε k V k .
As an important remark, it may be convenient to work with pq/ p 2 + q 2 .V instead of V . Thus,

V 1 = {pj, 1 ≤ j ≤ q -1} ∪ {qi, 1 ≤ i ≤ p -1}, V 3 = {0} ∪ V 2 ∪
{pq} and hence, the elements of V are all integer numbers. m(γ 0 ) is then given by

m(γ 0 ) = 2N (p+q-1) k=1 ε k V k 2N pq .
As a consequence, m(γ 0 ) is a rational number whose denominator and numerator are explicitly known.

• Computation of the sequences (i k ) and (j k ) Let I 1 and J 1 be the two following lists

I 1 = {1, 1, . . . , 1
, 0, 0, . . . , 0 } and J 1 = {0, 0, . . . , 0 , 1, 1, . . . , 1 } q -1 times p -1 times q -1 times p -1 times .

This means that the numbers 1 which appear in the sequence I 1 correspond to the points P k which belong to horizontal lines and the numbers 1 of the sequence J 1 correspond to the points P k belonging to vertical lines. From these two lists and from the permutation σ, we define

I 2 = σ(I 1 ) = {I 1 σ(1) , I 1 σ(2) , . . . , I 1 σ(p+q-2) } and J 2 = σ(J 1 ) = {J 1 σ(1) , J 1 σ(2) , . . . , J 1 σ(p+q-2) }
and also

I 3 = 0, I 2 1 , 2 k=1 I 2 k , . . . , p+q-2 k=1 I 2 k and J 3 = 0, J 2 1 , 2 k=1 J 2 k , . . . , p+q-2 k=1 J 2 k .
Finally, we set

I = I 3 ∪ (p + I 3 ) ∪ • • • ∪ ([2N -1]p + I 3 ) and J = J 3 ∪ (q + J 3 ) ∪ • • • ∪ ([2N -1]q) + J 3 .
Then, for all k, 1 ≤ k ≤ 2N (p + q -1), i k = 1 + I k and j k = 1 + J k . Let us introduce the matrix A defined from M in (3.3) and a function r defined over integers by

r(k) ∈ {1, 2, . . . , 2N } and ∃ l ∈ Z | k = 2N.l + r(k).
Then, for all k,

1 ≤ k ≤ 2N (p + q -1), ε k = A r(i k ),r(j k ) = A r(1+I k ),r(1+J k ) .
There are two reasons why we consider all rays of angle arctan q/p at the same time in the computation of m p,q . First, all these rays have the same sequence V k . In addition, let γ = [X 0 , arctan( q p )] where X 0 = (x 0 , y 0 ) has integer coordinates. Then, the sequences (i k ) and (j k ) of γ can be computed from the lists I k and J k by the formula:

i k = 1 + x 0 + I k and j k = 1 + x 0 + J k .
For two relatively prime integers p ≥ 1 and q ≥ 1, the number m p,q can be computed in the following way 1. compute the G.C.D. d of p and 2N and from Proposition 3.2, the 2N starting points with integer coordinates that must be considered are known. Let us note X 1 , X 2 , . . . , X 2N and Y 1 , Y 2 , . . . , Y 2N their coordinates.

2. Compute the three lists of 2N (p + q -1) elements V k , I k and J k defined above.

3. m p,q is then the minimum of the 2N numbers

2N (p+q-1) l=1 A r(1+X k +I l ),r(1+Y k +J l ) V l 2N pq .
All these quotients have the same denominator and hence, are easy to compare by looking at their numerator. Finally, this gives the explicit value of m p,q .

We now present the results obtained with our algorithm for explicit domains ω. As an example, for the computation of g(ω) for the domain ω of Figure 7, the minimum for vertical and horizontal rays is g = 1/3 and there are 45 families of oblique rays of first kind (i.e. the rays of part 3 in algorithm). Among these rays, there exists γ such that m(γ) = 1/3 but there is no γ such that m(γ) < 1/3. At this step, the value of g is 1/3. There are also 344 families of oblique rays of second kind (corresponding to part 5 of algorithm). None of them satisfies m(γ) = 1/3. We obtain g(ω) = 1/3. Figure 11 presents the values of m p,q as a function of pq and presents also inequality of Theorem 3.1. Note that this inequality is not optimal for this particular domain. However, (3.2) is optimal for a unique square C i,j . This shows that the error comes from the summation of inequalities (3.2) for all the squares of ω T . Nevertheless, it is useful because it certifies that the value of g(ω) is exact.

There exist 10 rays which satisfy m(γ) = g(ω); six vertical or horizontal rays (more precisely six families of vertical or horizontal rays). They are represented on Figure 12.a. There are also two rays of angle π/4 represented on Figure 12.b, one ray of angle arctan 1/2 represented on Figure 12.c, and also the ray γ = [0, arctan 1/4] represented on Figure 12.d.

The domain ω of Figure 13 of area |ω| = 29/100 is represented here to show that intuition can be false. Indeed, consider only vertical rays, horizontal rays and closed rays of small period. The intuition says that g(ω) = 1/5. However, the ray γ = [0, arctan 8/7] is such that m(γ) = 111/560 (note that 1/5=112/560), that is the exact value of g(ω) as shown by the complete computation. Thus, let us set L = T . Clearly, t n can be assumed to be a multiple of L. Indeed, replacing t n by t n + s n (where |s n | ≤ L) does not change the limit of m(γ n tn ). Now, assume that

θ n = θ. If tan(α) ∈ Q or if tan(α) = ∞, then clearly lim n m(γ n tn ) -m(γ n ) = 0. If tan(α) ∈ R\Q,
(ω) ≥ lim inf n m(γ n ) ≥ g ′ (ω).
This proves (4.2). Hence, we can assume that

θ n = θ. (4.5)
Now, let us define, for k ∈ {0, ..., tn L -1}, X k,n = γ n (kL) and γ k,n (t) = γ n (kL+t) for t ∈ [0, L]. Let us define also γ k,n,s as the unique trajectory of length L and slope θ such that γ k,n,s (s) = γ k,n (s) and

A k,n = s∈[0,L] γ k,n,s . γ k,n (0) = γ k,n,0 (0) γ k,n (s) = γ k,n,s (s) γ k,n,s γ k,n,N A k,n γ k,n,0 γ k,n γ k,n (N ) = γ k,n,N (N )

Now, we prove that

Step 1 There exists a sequence (k n ) n such that |A kn,n ∩ ∂ω| ≤ ǫ and m(γ kn,n ) ≤ g(w) + ǫ for all n large enough. Here, |A kn,n ∩ ∂ω| denotes the length of the curve A kn,n ∩ ∂ω.

In the following, the length of any curve C will be denoted by |C|. Let

K n = k ∈ {0, ..., t n L -1} s.t. m(γ k,n ) ≤ g(w) + ǫ . Set M = m∈∆   n≥m;k∈Kn X k,n   and M = m∈∆   n≥m;k∈Kn γ k,n   .
For X ∈ M, let γ X denote the trajectory of length L and slope θ such that γ X (0) = X. Note that M and M are not empty. Otherwise, K n would be empty too and we would have m(γ k,n ) ≥ g(ω)+ǫ for all n ≥ n 0 and forall k. Thus, we would have m(γ n tn ) ≥ g(ω) + ǫ that contradicts (4.3). Now, we prove that M = y∈M γ y .

(4.6) Take a sequence (X ln,n ) n such that lim n X ln,n = y ∈ M. Then, for all t ∈ [0, L], lim γ ln,n (t) = γ y (t). We obtain that y∈M γ y ⊂ M.

Conversely, if z ∈ M then there exist two sequences (l n ) n such that l n ∈ K n and (s n ) n ⊂ [0, L] such that z = lim n γ ln,n (s n ). Up to a subsequence, we can assume that there exist y ∈ M and s ∈ [0, L] such that lim n X kn,n = y and lim n s n = s. As one can check, this implies that z = lim n γ kn,n (s) = γ y (s) and therefore M ⊂ y∈M γ y .

This proves (4.6). We now distinguish two cases.

First, assume that there exists an infinite sequence (y

n ) n in M such that γ yn ∩ γ y n ′ = ∅ if n = n ′ .
, • • • , y k } ⊂ M such that γ yn ∩ γ y n ′ = ∅ if n = n ′
and assume that k is maximal. This means that for all y ∈ M, there exists n ∈ {1, ..., k} such that γ y ∩ γ yn = ∅ (otherwise the set {y, y 1 , • • • , y k } would have the above property and k would not be maximal). Since |γ y | = L, we have: γ y ⊂ γ ′ yn where γ ′ yn is the trajectory of length 3L + 2 and slope θ such that γ ′ yn (L + 1) = γ yn (0). Note that instead of γ ′ yn , one could have considered trajectories of length 3L. We need to consider trajectories strictly greater than 3L to get relation (4.10) below. For simplicity, we choose 3L + 2. Using (4.6), we see that

M ⊂ k n=1 γ ′ yn . (4.8)
Let n be fixed. Let

A n = t ∈ [0, t n ] γ n (t) ∈ k m=1 γ ′ ym
The set k m=1 γ ′ ym is a finite union of disjoint trajectories of finite length and slope θ. Moreover, θ n = θ (see (4.5)). Hence, A n is a discrete set of points. Since k m=1 γ ′ ym is closed, A n is closed too. This shows that A n is finite. Let now t 1 , t 2 ∈ A n with t 1 < t 2 . As one can check, there exists α > 0 independent of n such that if t ≤ α|θ n -θ| -1 , γ n (t From the definition of K n , we write that for l ∈ K n we have m(γ l,n ) ≥ 0 and we know that for l ∈ {0, ..., tn L -1}\K n , we have m(γ l,n ) ≥ g(ω) + ǫ. We obtain that m(γ n tn ) ≥ L t n # {0, ..., t n L -1}\K n (g(ω) + ǫ) = L t n t n L -#K n (g(ω) + ǫ).

Since lim n m(γ n tn ) = g(ω), t #K n ≥ ct n where c > 0 is independent of n. It follows from (4.9) that we can choose k n ∈ K n such that [k n L, (k n +1)L]∩A n = ∅. Hence, γ kn,n ∩ k m=1 γ ′ ym = ∅. We can assume that lim n X kn,n = y ∈ M. Then, for all t ∈ [0, L], we have: lim n γ kn,n (t) = [y, θ](t). Since γ ′ ym has been chosen such that their length is 3L + 2, there exists an m such that We have 0 < d n < d ′ n . Since the sequence of sets (A kn,n ) n converges to γ y (see figure above) and since γ y ⊂ γ ′ ym , it is clear that lim n d ′ n = lim n d n = 0. After passing to a subsequence, we can assume that for all n, d ′ n+1 < d n . In other words, the sets A kn,n can be assumed to be all disjoint. Since |∂ω| is finite, there exists a infinite number of A kn,n such that |A kn,n ∩ ∂ω| ≤ ǫ. We can assume that, for all n, |A kn,n ∩ ∂ω| ≤ ǫ. Since k n ∈ K n , this proves Step 1 in this case. Note that the sequence (k n ) n does not necessarily tend to +∞.

Let now γn = γ kn,n . Keeping the same notation as in the definition of A k,n . Furthermore, let γn 0 = γ kn,n,0 . This means that γn 0 is the unique trajectory of slope θ and length L such that γn 0 (0) = γn (0). We now prove that

Figure 2 :

 2 Figure 2: Point of view of flat torus

Remark 1 . 1 Proposition 1 . 3

 1113 The assertion (0.3) follows immediately from Propositions 1.1 and 1.2. Moreover,let γ ∈ C. If γ is open, we have m(γ) = |ω| and if γ is periodic of period L, we have m(γ) = 1 L L 0 χ ω (γ(s))ds.As one can check, an immediate consequence of Proposition 1.2 is the following result Let ω ⊂ Ω be Riemann-integrable, then g(ω) ≤ |ω|.

Figure 4 :

 4 Figure 4: Closed ray p = 3 and q = 2 in the flat torus

Figure 5 :

 5 Figure 5: Ray γ = [0, α] with tan α = 4/15

. 1 )

 1 If k = 0 or k = R, equation (3.1) remains true. Hence, in all cases 1

Figure 7 :

 7 Figure 7: A domain ω for N = 6 Let us also define the 2N× 2N matrix A such that A i,j = 1 if C j,i ⊂ ω T , A i,j = 0 if C j,i ⊂ ω T , i.e. M i,j = A i,j = A 2N +1-i,j = A i,2N +1-j = A 2N +1-i,2N +1-j . (3.3)

Figure 9 :

 9 Figure 9: Case of a ray which does not meet any point with integer coordinates Let A i be the intersection point of the line meeting A and directed by u (the points A solutions of the minimization problem above are clearly on a same line directed by u) and the line belonging to the lattice Z + Z which contains B i (see Figure 9 for the case N = 2). In the same way, there exists C with integer coordinates which satisfies d(C, γ) = min{d(P, γ)|P has integer coordinates and d(P, γ) < 0}.

Figure 10 :

 10 Figure 10: Ray γ 0 , for N = 2, p = 3 and q = 2

2 Figure 11 :

 211 Figure 11: An example of computation of g(ω)

Figure 12 : 3 Figure 13 :

 12313 Figure 12: Minimizing rays : m(γ) = g(ω) = 1/3

4

  Appendix : proof of Theorem 2.1 First, it is clear that g(ω) ≤ g ′ (ω).(4.1)Indeed, for all γ ′ ∈ C and all t > 0, m(γ ′ t ) ≥ inf γ∈C m(γ t ). Hence,m(γ ′ ) = lim sup t→+∞ m(γ ′ t ) ≥ lim sup t→+∞ inf γ∈C m(γ t ) = g(ω).Since this equality is true for all γ ′ ∈ C, this shows (4.1). Let us prove thatg(ω) ≥ g ′ (ω).(4.2)Let us fix ǫ > 0 and choose a sequence (γ n ) n ⊂ C and a sequence (t n ) n which tends to +∞ such thatlim n→+∞ m(γ n tn ) = g(ω).(4.3)For all n ∈ N, there exist X n ∈ Ω andθ n ∈ [0, 2π[ such that γ n = [X n , θ n ].Up to a subsequence, we can assume that there exists (X 0 , θ)∈ Ω × [0, 2π] such that lim n X n = X 0 and lim n θ n = θ.We claim that there exists L > 0 such thatm([y, θ] L ) ≥ g ′ (ω)ǫ for all y ∈ Ω.(4.4)If tan(θ) ∈ R\Q, then set L = t 0 , where t 0 is as in Proposition 1.1. Indeed, together with relation(2.1), m([y, θ] L ) ≥ |ω|ǫ ≥ g ′ (ω)ǫ. If tan(θ) ∈ Q or if tan(θ) = ∞,the ray [y, θ] is periodic and the period T does not depend on y ∈ Ω. Hence, m([y, θ] L ) = m([y, θ]) ≥ g ′ (ω).

A

  [y, θ] L ⊂ γ ′ ym (4.10) with [y, θ](0) = γ ′ ym (0) and [y, θ](L) = γ ′ ym (L). As one can check, this implies that A kn,n ∩ k m=1 γ ′ ym = ∅ (see figure below). kn,n A k n+1 ,n+1 γ k n+1 ,n+1γ kn,n By (4.7), we obtain thatA kn,n ∩ M = ∅. (4.11) Now, set d n = dist(A kn,n , γ ′ ym ) = inf X∈A kn ,n dist(X, γ ′ ym ) and d ′ n = sup X∈A kn ,ndist(X, γ ′ ym ).

  It is said to be open if it is not closed. Indeed, for example using the point of view of a flat torus, the trajectory is periodic if and only if there exist 0 ≤ t 1 < t 2 and n, m ∈ N such thatx 0 + t 1 cos α = x 0 + t 2 cos α + 2n y 0 + t 1 sin α = y 0 + t 2 sin α + 2m . Let γ = [X 0 , α]be an open ray. Then, {γ t , t ≥ 0} is dense in the torus T and then in Ω. In addition, if ω is quarrable (i.e. χ ω Riemann-integrable on Ω) then m(γ t ) ----→

	Hence 2m(t 1 -t 2 ) cos α -2n(t 1 -t 2 ) sin α = 0. Let us now consider open rays. They have the
	following properties (see for example [5] p. 172).
	Proposition 1.1

We have the following characterization. The ray [X 0 = (x 0 , y 0 ), α] is open if and only if cos α and sin α are independent over Z, i.e. if and only if tan α ∈ R -Q. t→+∞ |ω|.

  this relation follows from Proposition 1.1. Then, by relation (4.3), it follows that g

  Since |∂ω| is finite, one can choose y ∈ M (y is one of the y n ) such that |γ y ∩ ∂ω| ≤ ǫ 2 . Otherwise, for all n, |∂ω ∩ γ yn | ≥ ǫ 2 and hence, since γ yn ∩ γ y n ′ = ∅, we would have +∞ = This is false. The definition of M implies that there exists a sequence (k n ) n such that y = lim n X kn,n with k n ∈ K n . Clearly, for all t ∈ [O, L], Set B n = m≥n A kn,n . Obviously, B n is a decreasing sequence of sets. We recall that By construction, for all t ∈ [0, L], γ kn,n,s (t) = γ y (t). This implies that n∈N B n = γ y . Since |γ y ∩ ∂ω| ≤ ǫ 2 , for all n large enough, we have |B n ∩ ∂ω| ≤ ǫ. Since A kn,n ⊂ B n and since k n ∈ K n , this proves Step 1 in this case. Now, assume, for all infinite sequences (y n ) n in M, there exists n = n ′ such that γ yn ∩ γ y n ′ = ∅. Clearly, this case occurs if M is finite. Then, choose a finite set {y 1

	A kn,n =	γ kn,n,s
		s∈[0,L]
	lim n	γ kn,n (t) = γ y (t).	(4.7)

n |∂ω ∩ γ yn | = |(∪ n γ yn ) ∩ ∂ω| ≤ |∂ω|.

  Then, it is clear that the trajectory γ n , whose slope is θ n , meets two different segments of k m=1 γ ′ ym in a time proportional to the difference |θ n -θ| of the slopes. Hence t 2t 1 ≥ α|θ n -θ|

	k m=1 γ ′ ym . Indeed,	k m=1 γ ′

1 + t) ∈ ym is a finite union of segments of slope θ. -1 . This proves that #A n ≤ t n α |θ n -θ|.

Influent rays

Let γ be a horizontal ray starting at X 0 = (x 0 , y 0 ). Then,

Assume that y 0 = k is an integer. Since each C i,j is closed,

Obviously, this ray does not realize the infimum in the definition of g. In the same way, for a vertical ray, only the numbers 1

must be considered. Now, let us deal with oblique rays and fix α. Let us denote tan α by q/p, where p and q are relatively prime integers.

Remark 3.1 One has to consider only the rays defined by γ = [X 0 , α] with X 0 ∈ T and α ∈ [0, π/2], i.e. p ≥ 0 and q ≥ 0. Indeed, keeping the notations of Figure 8, the ray

In the same way, the rays

Let us now study the influence of the starting point of rays. We have the following result Proposition 3.1 Among oblique closed rays of angle α, the ray which spends the least time in ω in average is a ray which meets a point with integer coordinates .

Step 2 We have

for any n large enough.

The rays γn and γn 0 can be seen as segments of length L in the plane. Let p n be the projection on γn 0 in the direction of the line γn (L) γn 0 (L) . Thales' theorem implies that for all t ∈ [0, L], p n (γ n (t)) = γn 0 (t).

Then, there exists a point X of ∂ω between γn (t) and γn 0 (t). Thus, X ∈ [γ n (t), γn 0 (t)] ∂ω. This shows that p n (X) ∈ p n (∂ω A kn,n ). Indeed, remark that, for all t ∈ [0, L],

[γ n (t), γn 0 (t)] ⊂ A kn,n . Since γn 0 is parametrized by the length, the segments [0, L] and γn 0 can be identified. We obtain that

Now, write that

By (4.12), this gives

Remember that p n is a projection whose angle tends to π 2 . Hence, for any piece of curve C, |p n (C)| ≤ 2|C| (the constant 2 could be replaced here by a constant c n which goes to 1 with n).

It follows that

Step 2 is then a direct consequence of Step 1.

Step 3 Conclusion

The trajectory γn 0 has length L and slope θ. The definition of L (see (4.4)) then implies that m(γ n 0 ) ≥ g ′ (ω)ǫ. By Step 1, m(γ n ) ≤ g(ω) + ǫ.

Step 2 then shows that

Since ǫ is arbitrary, we obtain (4.2). Together with (4.1), the proof of the theorem is complete.


Keywords:

Generating optimal aircraft trajectories with respect to weather conditions

Goal: Compute optimal routes in Cruise Flight. Why? Increase Air Traffic Capacity and reduce time travel and fuel consumption. Assumption:

One aircraft

Several aircraft

Idea: Propagate the front in the configuration space of several aircraft. Example: for two aircrafts, state space the coordinates of both aircraft. Problem: Curse of dimensionality.

Proposed solution:

Use Approximate Dynamic Programming methods to compute good approximations and not the exact optimal trajectories. Profit: ≈ 30 seconds for 30 min of flight time;

1.9% of time saved for the trajectory.

Contacts

Brunilde Girardet -PhD Studentbrunilde.girardet@capgemini.com Laurent Lapasset -Engineer R&D ATMlaurent.lapasset@capgemini.com Virginie Aubreton -Manager ATM Unitvirginie.aubreton@capgemini.com where u is the optimal cost and F is the speed of the front in the normal direction 0 on the initial point


Laureline Guys

Laurent Lapasset

Harmonic and Biharmonic Navigation Functions for Conflict-free Trajectory Planning

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Harmonic and Biharmonic Navigation Functions for Conflict-free Trajectory Planning

Goal: Compute a trajectory for one aircraft with theoretical proof of static obstacle avoidance.

The obtained trajectories also have to satisfy Air Traffic Management requirements:

Navigation functions

Existing methods

Comparison of trajectories

New method