domain: math stat

text:
Fausto Galetto
email: fausto.galetto@gmail.com

Collatz Conjecture, new proof by merging into three SuperStates

Keywords: Quality Methods, Numerical Methods, Hailstone Conjecture, SPQR

published or not. The documents may come     Collatz Conjecture, new proof by merging into three SuperStates

Introduction

In a previous paper [START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF] we provided a probabilistic proof of the Conjecture; later, after we saw the interesting paper [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF]; both the papers tried to prove the Hailstone Conjecture using Markov processes. In another paper [START_REF] Galetto | Syracuse_Collatz Conjecture: Comparison of two Markov approaches towards the proof[END_REF], we compared the two probabilistic methods using the Reliability Integral Theory [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] and the SPQR Principle [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF]. Any probabilistic method makes "probable" the proof, but it is not really a mathematical proof. To overcome such a drawback later we showed a non-probabilistic proof using Flow Graphs and the SPQR Principle [START_REF] Galetto | Proof of Syracuse_Collatz Conjecture by Flow Graphs[END_REF].

The Collatz problem (also called the 3x+1 mapping, hailstone problem, Syracuse problem, ...), posed by L. Collatz in 1937, states that the system of the two difference equations, involving natural numbers, [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF] given the initial condition y 0 (any integer positive number) arrives after some (n is a number not known in advance) "continued" iterations to the value y n =1. It is considered a very difficult problem to be solved. As done in previous papers, we name "state of the system" the integer positive number generated by (1); so we see that the problem is transformed into the following:

given any initial state y 0 the system makes a certain number n of transitions (n is a number not known in advance) and finally it ends into the state y n =1. Any state of the system is a vertex in a graph. The rules [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF] give the next state of the system i.e. the next vertex in the graph: the edge traversed at time k+1 which we name e k+1 is (y k , y k+1 ).

Numerical experiments confirmed the validity of the conjecture for extraordinarily large values of the starting integer y 0 : it always reached 1 for all numbers up to 5.48 10 18 . (Oliveira e Silva 2008) The system (1) can be reduced to a non-linear difference equation, as the following one [START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF] The numbers y k+1 of the sequence [the state of the system] provided by the previous (Collatz) equations are sometimes named hailstone numbers. We can associate to any state of the system y k of the edge e k+1 =(y k , y k+1 ) traversed at time k+1 the index of the row of a matrix P and to state y k+1 the index of the column of the same matrix P; then we can describe the graph by the matrix P with entries 1 related to the arrow of the transition y k y k+1 for any edge e k+1 =(y k , y k+1 ). Then for any state of the system y k there is an infinite dimensional row vector u(k), with all entries u i (k)=0, but one entry u y (k)=1, related to the edge e k+1 =(y k , y k+1 ): it is a unit vector of vector space. The vector u(k) refers to the k-th iteration of a mapping T: the result of the mapping T to the vector u(k) is denoted u(k+1)=u(k)T. The vector u(k+1) is unit vector with all entries u j (k+1)=0, but one entry u y* (k+1)=1, where we have the subindexes y*y. The subindexes are according to (1): if u y (k)=1, then y=y k and the index y* of entry u y* (k+1)=1 of the vector u(k+1) has index y*=y k /2 IF y k is even, and y*=3y k +1 IF y k is odd. The mapping T [related to the graph] is provided by an infinite-dimensional matrix P=[a ij ], named transition matrix (with infinite rows and columns); rows and columns are indexed by the natural numbers (states of the system) 1, 2, 3, 4, ..., n, n+1, ...; every a ij entry is 0, except ........ [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] where the indexes i and j are given by ( 1), for the arrows e k+1 =(y k , y k+1 ). Accordingly we have u(k+1)=u(k)P (4) In the figure 1 we show the transition matrix; the 3 by 3 matrix with rows and columns indexed by the numbers 1, 2, 4, is highlighted due to its importance:  when the system is in the state 1, the next transition is to state 4: 1  4  when the system is in the state 2, the next transition is to state 1: 2  1  when the system is in the state 4, the next transition is to state 2: 4  2 All this means that when the system enters one of those 3 states [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] it never leaves out of them, the system (or the process) circulates in the set [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] forever. It is a "periodic process".

We can arrange the (infinite) matrix P with a SuperState SS 0 made of the 3 states [1, 2, 4], a SuperState SS 1 made of the infinite EVEN states [START_REF] Galetto | Syracuse_Collatz Conjecture: Comparison of two Markov approaches towards the proof[END_REF]8,10, …], a SuperState SS 2 made of the infinite ODD states [3, 5, 7, …] The matrix P can be partitioned into 6 submatrices, written simply as where P 00 , P 11 and P 22 are square matrices.

Notice that the submatrix P 00 is orthogonal: its inverse is its transpose

= .
It is important to notice that P 3 , the 3 rd power of the matrix P, is such that the submatrix [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF] is the identity matrix; when the system reaches the set 1, 2, 4 of the states it remains there forever. It follows that = = . The matrices P 00 , P 11 and P 22 are square matrices, while the others are rectangular; all are, given more explicitly by SS 0 1 0 0 1 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 2 1 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 4 0 1 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. SS 1 6 0 0 0 0 0 0 0 0 0 0 0 0 …. 1 0 0 0 0 0 0 0 0 0 …. 8 0 0 1 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 10 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 1 0 0 0 0 0 0 0 0 …. 12 0 0 0 1 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 14 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 1 0 0 0 0 0 0 0 …. 16 0 0 0 0 1 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 18 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 1 0 0 0 0 0 0 …. 20 0 0 0 0 0 1 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 22 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 1 0 0 0 0 0 …. 3 0 0 0 0 0 1 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 5 0 0 0 0 0 0 0 0 1 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 7 0 0 0 0 0 0 0 0 0 0 0 1 …. 0 0 0 0 0 0 0 0 0 0 …. 9 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 11 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 13 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 15 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 17 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 19 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 …. 21 0 0 0 0 0 0 0 0 0 0 0 0 …. 0 0 0 0 0 0 0 0 0 0 ….

= ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ = 0 0 1 1 0 0 0 1 0 = 0 0 0 0 0 0 0 0 0 … … … = 0 0 0 0 0 0 0 0 0 … … … = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … … … … … … … … … … … ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ SS 0 SS

The transition graph of the merged Markov Process

Please see the infinite transition stochastic matrix P of figure 1, partitioned into 6 submatrices, = 0 0 where P 00 , P 11 and P 22 are square matrices (noticing that P 00 refers to the set 1, 2, 4 of the states), given more explicitly by matrix P in the introduction. The process is a "periodic" with period 3: when the system enters one of the 3 states [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] it never leaves the set 1, 2, 4, the system (or the process) circulates in the set 1, 2, 4 forever. P 3 , the 3 rd power of the matrix P, is such that the submatrix [see formula [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF]] is the identity matrix; when the system reaches the set 1, 2, 4 of the states it remains there forever because the rectangular submatrices and in the upper right corner have only 0 entries. The process is bound to enter the SuperState SS 0 =1, 2, 4 because the rectangular submatrix in the middle left corner has only one 1 entry [the other entries are all 0] and the rectangular submatrix in lower left corner has only 0 entries. The "periodic process" circulating in the set 1, 2, 4 is ruled by the submatrix P 00 .

The graph of the transitions is given in figure 2. In the figure 3 we show the flow graph of the 3 SuperStates SS 0 , SS 1 and SS 2 (of the merged process) and the transitions between them; notice that there are three arrows from SS 1 , one back to SS 2 , one forward to SS 0 and one re-entering into SS 1 (which accounts for the internal transitions within SS 1 ).

Figure 3. The graph of the transitions (of the merged process) between the SuperStates SS 0 , SS 1 and SS 2

The merged process is ruled by a matrix P merged as the following where the transition probabilities are shown (we shall see later how to find the probabilities p 10 and p 11 ). IF p 10 >0, the matrix P merged provides the "steady state probability vector" =[1, 0, 0] solution of the relationship =P merged , which states that the process stays forever in the SuperState SS 0 after entering it.

After entering SS 0 the probability of being in the states [making the SuperState SS 0 ] 1, 2, 4 (Collatz cycle) is given by the "steady state probability vector" *=[1/3, 1/3, 1/3] solution of the relationship *=*P 00 . IF p 10 >0, another way of finding the "steady state probability vector" is by using the theory given in the books [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] related to Reliability Integral Theory [RIT]; one can find two vectors z 1 and z 2 defined, as follows,  z 1 is the vector of the (steady state) probabilities of entering into the SuperState SS 0 , when there is a transition SS 1 =even states  SS 0 =1, 2, 4.  z 2 is the vector of the (steady state) probabilities of entering into the SuperState SS 1 =even states coming from SS 0 . z 1 , in the case of the merged process, is by definition a one-dimensional row vector [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF] (which is by the way the 1 st entry of the vector =[1, 0, 0]) related to the SuperState SS 0 ; it is found with no calculations, only by inspection of the figure 3. z 2 , in the case of the merged process, is by definition a two-dimensional row vector [0, 0] (which is by the way the last two entries of the vector =[1, 0, 0]) related to the SuperState SS 1 and SS 2 ; it is found with no calculations, only by inspection of the figure 3. Now we need only to find the value of the probabilities p 10 and p 11 . Let's start with p 11 and look at the matrix of figure 1, in particular to the infinite square submatrix P 11 . Let's assume, for a while, that the dimension are a finite couple (2m, 2m); the number of 1 entries are (m-1); then the ratio, the probability p 11 , is (m-1)/2m=0.5-1/2m> 0.5 -1/[2(81m)]. The matrix P 12 , for a while, can have the same dimension (2m, 2m). IF the initial condition y 0 (any integer positive number) is an odd number, then the 1 st iteration provides an even number 3y 0 +1=m; we decide to give to the matrices P 11 , P 12 , P 21 , P 22 , the dimension (2m, 2m); in order to take into account the possibility that, at some iteration k, there could be a transition y k-1 y k , with y k >2m, we choose for the above 4 matrices a dimension m'=2(3 4 m)=2(81m); finally we set p 11 =0.5 -1/[2(81m)]. It follows that p 10 =1/[2(81m)]. This argument can be repeated for any finite initial condition y 0 . We always compute a probability

SS0 SS1 SS2

p 10 >0 and we are certain that the "steady state probability vector" =[1, 0, 0] solution of the relationship =P merged exists.

The merged process stays forever in the SuperState SS 0 after entering it. For any k the iterated value y k cannot go to infinity, as proved in [1 by Carletti et al.]

Conclusion

Having applied the SPQR («Semper Paratus ad Qualitatem et Rationem») Principle, the author thinks that his new probabilistic method is able to provide the proof of the Syracuse_Collatz Conjecture [he did already probabilistically in a previous paper].

  …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. ….

Figure 1 .

 1 Figure 1. The (infinite) transition matrix P [only a part is shown], with the 3 SuperStates

Figure 2 .

 2 Figure 2. The graph of the transitions within and between the SuperStates SS 0 , SS 1 and SS 2 (only few of the total transitions are shown)

4 6 8 10 12 14 16 18 20 22 3 5 7 9 11 13 15 17 19 21

	1	SS 2
	EVEN states (but 2, 4)	ODD states (but 1)
	State 1 2


Chloé Artaud
email: chloe.artaud@univ-lr.fr

Antoine Doucet
email: antoine.doucet@univ-lr.fr

Vincent Poulain D'andecy
email: vincent.poulaindandecy@yooz.fr

Jean-Marc Ogier
email: jean-marc.ogier@univ-lr.fr

Automatic Matching and Expansion of Abbreviated Phrases without Context

Keywords: abbreviations, string distance, information extraction

In many documents, like receipts or invoices, textual information is constrained by the space and organization of the document. The document information has no natural language context, and expressions are often abbreviated to respect the graphical layout, both at word level and phrase level. In order to analyze the semantic content of these types of document, we need to understand each phrase, and particularly each name of sold products. In this paper, we propose an approach to find the right expansion of abbreviations and acronyms, without context. First, we extract information about sold products from our receipts corpus and we analyze the different linguistic processes of abbreviation. Then, we retrieve a list of expanded names of products sold by the company that emitted receipts, and we propose an algorithm to pair extracted names of products with the corresponding expansions. We provide the research community with a unique document collection for abbreviation expansion.

Introduction

In the general objective of detecting false documents by verifying the information contained in the document, we must extract and model this information in order to be able to compare it with information that we will search for in external resources. However, administrative documents, such as payslips, administrative forms, invoices, proofs of purchase, have many constraints, particularly with regard to the document layout and the space available for each bit of information. Indeed, administrative documents, except for letters and contracts, are intended to be sufficiently concise and clear to be analyzed at first glance by humans.

This conciseness is often expressed by a layout containing precise tables and locations for the different elements specific to each type of document. For instance, in an invoice, we will often find a logo in the upper part, a header containing metadata, a table with names of products or services on the left, prices on the right, a total amount below, and the fine print at the end of the document. This highly organized structure imposes spatial constraints on textual and graphical elements: all the information necessary for the usefulness of the document must fit into a single document, often a single page for practical reasons. While logos and other graphic elements can be reduced, the textual information must be shortened while remaining sufficient to be understandable.

This constraint, common to many document types, allows us to observe the linguistic phenomenon of reduction. These abbreviations, that appear in many forms, are a bottleneck for the automatic analysis of document information. Indeed, it is very difficult to extract and interpret information that is not exhaustive and not fully explicit. We must therefore seek to associate abbreviations with their full form, or "expansion".

The task of associating abbreviations with their possible expansions is not simple because it involves many constraints: the absence of natural language context, the diversity of the types of abbreviations, the double level of abbreviation in words and in phrase, the ambiguity of the product names...

In Section 2 of this paper on related work, we show that the context-less automatic matching of abbreviations and their complete forms is a problem that has not been much studied in the state of the art. Section 3 presents our data set and analyses the different type of shortened forms observed. Section 4 explains the proposed approach for pairing abbreviated phrases and their possible expansions. Section 5 describes and discusses the results of this approach. We finally conclude and provide perspectives in Section 6.

Related Work

French Linguistics Definitions

French linguistics grammar does not much describe abbreviations in the French language, their socio-linguistic and semantic uses and values. For example, Riegel et al. only grant two pages and is focused in truncation and initialism only [START_REF] Riegel | Grammaire methodique du francais[END_REF]. The use of abbreviations are anecdotal to this work as it only belongs to the scriptural aspect of the language and is specific to each writer. To define the abbreviations, it is the graphic aspect that also prevails for Grevisse and Lits [START_REF] Grevisse | Le petit Grevisse: Grammaire française[END_REF], except for the phenomenon of reduction, which is the construction of a new form from another having the same meaning, by removal of a part of the full form. Similarly, acronyms enter the current language by becoming a word, as for instance "AIDS" in English. Grevisse and Lits [START_REF] Grevisse | Le petit Grevisse: Grammaire française[END_REF] further classify measurement units as symbols, not abbreviations, noting that units (in metrology or chemistry, for example) have lost their abbreviation value to take a symbolic value and are no longer followed by periods.

While the abbreviations in these two reference works are purely personal graphic practice, for Martinet [START_REF] Martinet | Éléments de Linguistique Générale[END_REF], on the contrary, the abbreviations are used to communicate while providing the least effort. In the case of abbreviations, it is a question of keeping the strict necessary to transmit information and thus saving memory, time and space. The abbreviation is an integral part of the evolution of the language: the more frequently an expression is pronounced, the more likely it is to be abbreviated, by eliminating non-specific elements, by truncation or by initialism.

Abbreviations Disambiguations

To our knowledge, little work exists in Natural Language Processing on the matching of all types of abbreviations with their expansions. However, we can find many works on the extraction of acronyms (often confused with the term "abbreviations") in texts and their disambiguation according to context. This application is particularly present in Biology and Medicine, where acronyms are very numerous, both in academic articles, especially on MEDLINE 4 , and in clinical reports.

These studies [START_REF] Yeates | Automatic extraction of acronyms from text[END_REF][START_REF] Yu | String similarity search and join: a survey[END_REF][START_REF] Larkey | Acrophile: An automated acronym extractor and server[END_REF] first attempt to extract abbreviations from the text. Authors use pattern-matching rules for mapping an abbreviation to its full form: acronyms are often capitalized, and sometimes in brackets when they appear for the first time [START_REF] Nadeau | A supervised learning approach to acronym identification[END_REF]. They then use context-based machine learning methods to choose the right expansion from a number of different dictionaries of acronymexpansions pairs, as explained by Gaudan et al. [START_REF] Gaudan | Resolving abbreviations to their senses in medline[END_REF]. These methods achieve very good results, but are not applicable to our data.

String distance methods

Our data are only strings of abbreviated forms and expansion forms, without context. For this reason, we can only work with string-based methods. The best known metric for calculating a distance between two strings is the Levenshtein distance (also known as the edit-distance) [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. It gives the smallest number of character changes (deletion, insertion, substitution) to switch from one string to another. The weaker the result, the less differences between strings. Numerous variants have been proposed for this metric, in order to take into account also the transpositions (Damerau-Levenshtein) or only substitutions in strings of the same length (Hamming).

In our problem, the strings are of different lengths and only the inserts are of interest to us, at level of characters in words and at level of words in phrases. For this second step, we can place the problem in set theory, considering the phrase as a set of words, which allows us to use measures such as the Jaccard index or the overlap coefficient. The Jaccard index is a simple similarity coefficient between two sets, defines as the size of the intersection divided by the size of the union. This index is between 0 (nothing in common) and 1 (identical sets).

Data Collection

We manually created a corpus of 248 product names as typed on sales receipts from a single store. These product names, constrained to be comprehensible for human while being limited to 20 characters, contains many reductions, both at level of words and at level of phrase, and many other obstacles to matching short and long forms.

Reductions

Abbreviations. In our receipts corpus, the abbreviation is a graphic phenomenon: the word is written in a short form by deleting some of its letters. We find two types of abbreviation in our corpus:

-Apocope: removal of the end of the word Apocope abbreviations may or may not be followed by a period (1a) and (1b). We notice that the period is followed by a space only in one case in our corpus. The rest of the time, it serves to separate a short form of a word from another word, in its short or long form. Our corpus contains a particular apocope type, that is not only a graphic phenomenon, but also phonetic and linguistic phenomenon: the word in its shortened form is so much used that it now exists in everyday language. This is the case of "BIO", which is an abbreviation of "biologique" ("from organic farming"). -Syncope: deletion of letters inside the word Syncope abbreviations also may or may not be followed by a period. We note that sometimes the first and last letters are kept (2a), but more often it is three representative consonants (2b). In other cases, some vowels are deleted in the word (2c).

These different forms of abbreviations present a particular challenge for their recognition: it seems that there are no systematic rules, or pattern, for the construction of abbreviations in this corpus, apart from the presence of the first letter of the word. Table 1 shows some examples of abbreviations, with the expansion of every word, the phrase expansion, the expansion of the corresponding expression in our corpus of expansions and a translation into English.

Initialisms. The first letters of each word of a compound word or of a brand name composed of several words are assembled. If the initialism is pronounced as a word, we consider it as an acronym. In our corpus, initialisms are sometimes followed by a period, contrary to the typographical rules.

Table 2 shows a few examples of initialisms of our data. We can notice that in the three examples, initialisms take the first letter of the prepositions "de" ("of ") and "à" ("to") contrary to the use.

Symbols.

Words are sometimes represented by (or contain) mathematical symbols. We thus frequently find the symbols "+" and "/". These special characters create segmentation problems. Their heterogeneous use does not allow systematic treatment. Indeed, in Table 3, we can see that the slash character can separate words (abbreviated or not) to mean a mixture of ingredients (1), whereas in [START_REF] Grevisse | Le petit Grevisse: Grammaire française[END_REF], the slash intervenes between two words (preposition and noun) of the same unit of meaning. It should be noted that this abbreviation "s/s" may correspond to the bigram "without sugars" but also "without salt" in our corpus. The slash is also observed in its signifying form of mathematical symbol [START_REF] Martinet | Éléments de Linguistique Générale[END_REF]. In this last case, we can not define the slash as a separator because the digit-slash-digit set, a mathematical fraction, constitutes a single semantic unit: "half". Other mathematical symbols are frequently used in cash register abbreviations, such as the plus sign and the letter X, used in place of the multiplication cross. In (4), the sign "+" has a true mathematical value: it is to signify the addition of a numerical quantity to the quantity indicated before the character. On the other hand, in (5), the "+" character is inserted between two (abbreviated) words, denoting a product consisting of two entities. The "+" character represents, in both cases, the combination of two units that are not usually assembled, however, the treatment to be performed is not the same in the two examples. In the first case the character must be interpreted as a word to disambiguate, while in the second, the character must be considered as a separator not to be included in the words framing. Numbers. The mixture of digits and letters is particularly problematic in our data because we can not apply a general rule to treat it. Indeed, there are several cases where numbers and letters are mixed:

-Expressions of quantities, associating a number and the abbreviation of a standard measurement unit (85G : "85 grams") -Expressions of quantities, associating a number with an abbreviation of a word or a complete word (4FRT : "4 fruits", 4FROMAGES : "4 cheeses") -Number of units, represented by the letter "X" (here meaning "times") contiguous before or after the number (4X125G : "4 units of 125 grams") -Abbreviations mathematically symbolized, associating a fraction and letters (1/2ECR : "semi-skimmed") -Names of products or brands containing numbers and letters, which should not be separated (T45 : "type of flour") -Absence of spaces between letters and numbers (75 VDP OC RG BIO09 :

"organic red wine of year 2009")

Other problematic features

While the different forms of reduction in the corpus present issues of segmentation and analysis of the text, other characteristics, specific to the format of the document, must be highlighted. Indeed, the word segmentation of the receipts is made difficult by various typographic elements, such as the case used, the presence of periods of abbreviations, the absence of spaces or the concatenation of numbers and units of measure. In rare cases, no character (space, point) can identify the break between two words. In the following example, characters "X" and "G" following a number are lexical units themselves and have to be separated from the abbreviation "DESS.". Letter case. The characters of this corpus are all capitalized, which does not allow to easily visualize initialisms, as it is the case in most works on acronyms and abbreviations in natural language texts. Nor does it make it possible to distinguish proper names, such as brand names for example, which could have helped in the analysis of documents.

Diacritics. The corpus does not present any diacritic sign, that is, no accent or cedilla. This absence is also a handicap for the analysis because it can cause the ambiguity of certain words, such as PATE, which can correspond to pâte ("paste") or pâté ("pâté").

Punctuation. Some product names have dots that act as both segmentation characters and truncation signs. In the example 8XDOS.SENSEO CAPP., the words DOS (for dosette, "capsule") and SENSEO (brand) should be separated while integrating the period with the word preceding it, contrary to the space, to have the possibility to force the search for the long form of the word thereafter. Indeed, in this example, the lowest distance finds the word dos ("back") instead of the word dosette, which is impossible because of the presence of the point which means that the word has been abbreviated. However, segmentation should not be applied to the period between two digits, as in the example CRISTALINE 1.5L because it is a decimal number.

Pseudo-syntactic elements. Beyond the word scale reductions and problematic typographic elements previously explained, we also need to analyze reductions at phrase level, which we can consider as multi-word expressions, to allow us to better understand the difficulties of alignment between short forms and long forms. These elements concern the reduction processes used, not from a lexical point of view but from a syntactic and semantic point of view.

Ellipsis. Product names usually include only names and adjectives necessary for product distinction. Prepositions and determinants are omitted, except in rare cases. These ellipses do not prevent the understanding of product names, because these words are almost meaningless. However, some ellipses concern words that are more important for automatic understanding because they carry meaning, like in Example 2: it's semantic ellipses.

Example 2. 205G DESSERT NOIR : Chocolat noir Nestlé Dessert ("Dark Chocolate Nestlé Dessert")

Random word order. The order of words in product names is not always intuitive (300G MOUSSAKA BARQ instead of Barq[uette de] Moussaka, "tray of Moussaka"). Similarly, the order of words in similar products is not always the same.

Ambiguity of reductions. The reductions can be ambiguous, as we have seen in the state of the art. Thus, we find in our corpus some identical reductions that do not correspond to the same long form. For example, we find PDT for initials of Pomme de terre ("Potato") and for syncope of Président ("President").

Several reductions for a single long form. For some recurring words, we have noticed the diversity of reduced forms in receipts. For instance, we can find SLD., SAL, SALAD, SLDE and SALADE for salade ("salad"). We can notice that some shortened forms are finally not so much reduced in terms of characters. This is the case for example of PIZZ. which contains as many characters as PIZZA.

Spelling variants. Receipts also contain graphic or spelling variants of certain words. Sometimes these variants lengthen the word. For some brands, it is easier to simplify the spelling. This is the case of MINIBABY (for "Mini Babybel"), which is both a contraction of two words and an abbreviation.

Corpus of product names (possible expansions)

In order to find a less ambiguous form for each reduced forms present on the receipts, we have created a reference corpus containing a list of products whose names are detailed and unabbreviated.

We have thus extracted from the Web a list of 13 888 titles of products distributed by the Drive-in service of a supermarket of the same brand as that of our receipts. The Drive-in service allows you to shop online by choosing products with the information the site provides: detailed product name, price, price per kilogram, product weight, promotions and photography.

The choice of this supermarket brings an advantage and a disadvantage: it allows to have a larger choice of products, and therefore a broader reference corpus, but at the same time, the proposed products are not always the same as those bought in convenience stores. In fact, consumers are not the same in a small local area, located in a student district, where our receipts come from, and in a large area on the outskirts. The products sold are not the same either: we will mainly find in the minimarket meals (salad, sandwiches, ready meals), cupcakes and drinks individually, while we will find more fresh or unprepared products, in family quantity, in the supermarket.

These product names differ a lot from the product names extracted from the receipts. While brevity is required on the receipt, it is detail and accuracy that are most important on the purchase website, to be as exhaustive as possible so that the customer knows which product he buys without having it in front of him. The names of products from the Web are consequently longer (37 characters on average) and contain an average of 5.5 words. Each name product contains a key word, often one or several qualifying terms (adjective or noun) and end with the proper noun of the product or the brand, such as the following example. We can however observe some irregularities in these formulas such as repetition of a part of the phrase. There is also some abbreviated words (current initialisms or truncations such as "choco" or "PDT"), ellipses of prepositions ("chocolat lait" instead of "chocolat au lait" for "milk chocolate"), numbers and symbols.

Proposed approach

We want to find the best long form for each shortened term of our receipts corpus. Matching a shortened term with its full form without context is a very difficult task, especially when the shortened term is so noisy.

Automatic pre-processing

Our previous analysis allows us to note the main differences between our two datasets. First, the shortened form is totally uppercase and does not contain any diacritics. In order to make the source (receipts terms) and the target (web extracted terms) comparable, we normalized all target characters to capitalize them and delete all diacritics.

Then, we have to segment both receipts terms and web terms into words, considering the difficulties explained below concerning symbols and absence of space. According to the case, we consider one or two tokens around a symbol like "+", "/", ".". We also separate in two tokens the numbers followed by more than 2 letters, such as 4FROMAGES ("4 fromages" for "4 cheeses"). We choose the 2-letters limit to avoid to separate the numbers followed by symbol of quantity, like in 75CL ("75 centilitres" for "75 centiliters")

We also define the list of the most frequent trigrams of the web terms, to create a dictionary of most probable initialisms. Indeed, we previously noticed that all initialisms of our receipts corpus are composed of three letters, and correspond to frequent multi-word expression, such as PDT. Thus, for each 3letters word in receipt expression, which is not a real word, we try to figure whether it could be an initialism.

Automatic matching

Terms of receipts are abbreviated both at the word-and at the phrase-level. This requires to implement a two-step algorithm.

First, we calculate the distance between words of shortened form and each word beginning with the same letter as the product names extracted from the web. We save the words within a short enough distance with the source word, or the initialism. To calculate this distance, we use a weighted Levenshtein distance for the first step, which allows us to put a different weight to each editing operation: substitutions, deletions and insertions. We multiply the cost of each operation by the corresponding chosen weight instead of incrementing by 1. In the case of the search of minimal distance between a shortened form and a long form, we want to have a lower weight for insertion than for the two others. We find after computation that the better weights for deletions and substitutions are 11, leaving insertions with a cost of 1, to obtain the better matching. If no distance is satisfactory, no word is recorded.

For the second step, we propose and compare two different methods. The first one is the weighted Levenshtein distance. From the first step, we obtain a list of probable words that we concatenate to have a phrase we can compare with each web phrase, calculating the distance between them. As for the word level step, we save the expression that have the minimal distance with the source phrase and the best weight is 11. The one is the Jaccard index, using the intermediary list of words obtained from the first step, as a set. We save the expression that have the higher index (included between 0 and 1).

Experiments

Ground truth

To evaluate our approach, we create a ground truth, manually associating receipts forms and web forms in a JSON format. We encounter some difficulties, because human does not always understand the reduction form, or cannot disambiguate between two similar products with different brands. For example, the PET 1.25L EAU GAZ form should correspond to one item of the 6 full forms list, each corresponding to a different brand, but we can not know which one, and our approach could not either.

For these cases of impossible disambiguation, we propose all the possibilities in our ground truth, to not have false negatives. In some cases, the products on the original receipts are not sold by the Drive-in service, and thus have no shortened form in our corpus. Such cases are evidently discarded in the evaluation.

Results and discussions

Results are measured based on the binary match between the proposed long expression and the ground truth, which can return "True" or "False", depending on whether the proposed long expression is the correct one or not. In addition, cases when no ground truth is associated to the abbreviation are ignored (cases that were not annotated or cases when even the human evaluator cannot perform the task). Thus we compute a percentage of correct answers, which is 36,87% for the best combination of weights in weighted Levenshtein method, and 33,64% for the Jaccard index method.

We observe that the Jaccard approach does not perform as well as the method based on weighted Levenshtein. This is due to marks of plural on many words: while the edit distance increases by 1, the Jaccard index does not recognize the same word. For example, OIGNON JAUNE, corresponding to Oignons jaunes (plural) in web source (for "Yellow onion"), with the intermediary list of words containing [OIGNON (singular), JAUNE (singular)]. The Jaccard index between the intermediary word set and the web word set is zero, resulting in a wrong answer. The weighted Levenshtein gives a score of 2 and provides the correct answer.

The traditional measures, namely Precision, Recall and F-Measure, are not the most appropriate to evaluate the performance of our system, because there is no prediction, only scores corresponding to distances. If we select the criteria distance = 1 for correct prediction and distance = 1 for wrong prediction, we obtain the results presented in Table 4. We only see with the first two results that when the distance is small, the result of the algorithm is always correct, but there are very few such cases. The next two lines show the maximal F-Measure we can find by changing the criteria of selection of relevant elements. Given that these evaluation results are not very conclusive, we propose an evaluation approach that allow a more qualitative evaluation of results. Only one third of our shortened phrase corpus is correctly found, but, when we analyze the results, we see that performance is not as weak, since the failed word is often the brand name, and most of the phrase if often correctly identified.

The Table 5 shows the average of the scores of three distances computed between the proposed phrases and the ground truth according to the method used. We can observe that there are only 16 edit operations between the two strings and that almost half of the words of the whole two phrases are common. The third line of Table 5 concerns the following test : we give the receipts forms to a French human and he has to find by himself what it could mean and to write the name of the product. We observe that the distance is more important than with our algorithm. This is explained by the addition of many keywords describing the product, as "boîte de conserve" (for "can").

Conclusion

The heterogeneity of product name reductions, whether in the diversity of reduced forms or more generally in the variety of reduction processes, the presence or absence of punctuation or the mixture of special characters, numbers and letters, makes rich the corpus analysis and complex its automatic processing. The automatic matching of shortened words and phrases with their expansion without context is an undeniable challenge. Indeed, the biggest part of people searching for matching abbreviations and expansions uses context to find relations between them in natural language or to disambiguate the meaning. Qualitative analysis of our experimental results are very promising and we think that the combination of the presented approach with an automatic analysis of contextual elements (like other products bought, hours of shopping...) would allow us to improve the choice of the better expansion for each shortened form.

To foster further research, we make the dataset and its ground truth available to other researchers within an ICPR 2018 competition5 .

Example 1 .

 1 Product name : 4X100GDESS.PANACHE Segmentation : 4 X 100 G DESS. PANACHE English gloss : four times one hundred grams of mixed dessert cream Typographic elements.

Example 3 .

 3 Céréales goût caramel/chocolat Lion (for "Caramel and chocolate flavored cereals named Lion")

Table 1 .

 1 Examples of Abbreviations

	Type	Abbreviation	Words expansion, Expansion and English gloss
	(1a) CONF.FIG.PROV.R.FR CONFiture FIGues PROVence Reflet FRance
			Confiture de figues de Provence Reflets de France
			Fig jam from Provence Reflets de France
	(1b) TAB CHO CRF NR BIO TABlette CHOcolat CaRreFour NoiR BIOlogique
			Chocolat bio noir 74% cacao Carrefour Bio
			Organic chocolate 74% cocoa Carrefour Bio
	(2a) PT BEUR.CHO LT NOI	PetiT BEURre CHOcolat LaiT NOIsette
			Biscuits petit beurre chocolat lait Petit Ecolier
			Butter cookies with milk chocolate Petit Ecolier
	(2b)	160G BLC PLT 4TR.F 160 Grammes BLanC PouLeT 4 TRanches Fines
			Blanc de poulet Carrefour
			Carrefour Chicken Breast
	(2c) PT DEJ.FRUITS RGES	PetiT DEJeuner FRUITS RouGES
			Biscuits petit déjeuner aux fruits rouges Carrefour
			Breakfast biscuits with red berries Carrefour

Table 2 .

 2 Examples of Initialisms

Initialisms

Expansion and English gloss 2X30CL VELOUT.PDT. Velouté de Pomme De Terre Cream of potato soup PT L'EVEQUE RDF Pont l'Eveque Reflet De France Pont l'Eveque Reflet de France YAF PANIER FRAM/MU Yaourt Aux Fruits Panier de Yoplait framboise/mûre Fruit yoghurt Panier de Yoplait raspberry/blackberry

Table 3 .

 3 Examples of Symbols

	Type	Initialisms	Expansion and English gloss
	(1) BURGER EMM/CHEDDAR	Burger emmental et cheddar
			Burger emmental and cheddar
	(2)	KRISPROLL.S/S	Krisprolls sans sucre
			Krisprolls without sugar
	(3)	BEURRE BIO 1/2 SEL	Beurre bio demi-sel
			Half -salt organic butter
	(4)	CHOCOLATINE X4 + 1 G	4 chocolatines et une gratuite
			4 chocolate croissant and one free
	(5)	DUO TERRIN+MOUS.CD Duo terrine et mousse de canard
			Duo terrine and duck mousse

Table 4 .

 4 Evaluation with traditional measures

	Method	Precision Recall F-measure Rejection Accuracy
	Jaccard index = 1	1.0	0.06	0.10	1.0	0.68
	Weighted-Levenshtein distance = 1	1.0	0.04	0.07	1.0	0.65
	Jaccard index ≥ 0.33	0.60	0.79	0.68	0.74	0.76
	Weighted-Levenshtein distance ≤ 50 0.47	0.69	0.56	0.54	0.59

Table 5 .

 5 Evaluation with distance measures

	Method	Success rate Jaccard Overlap Levenshtein
	Jaccard	33.64	0.44	0.45	15.98
	Weighted-Levenshtein	36.87	0.49	0.43	15.46
	Human		0.19	0.06	18.34

Medical Literature Analysis and Retrieval System Online, https://www.nlm.nih. gov/pubs/factsheets/medline.html

Fraud Detection Contest: Find it!: http://findit.univ-lr.fr


Jean-Marie Mirebeau

François Desquilbet

Worst case and average case cardinality of strictly acute stencils for two dimensional anisotropic fast marching

.

Introduction

This paper is devoted to the analysis of an approximation-like problem arising in the discretization of a class of Partial Differential Equations (PDE): eikonal equations, defined with respect to a possibly strongly anisotropic Finslerian metric. The results presented are related with the numerical solution of this equation on two dimensional cartesian grids, and their extension to higher dimension and/or to unstructured domains remains an open question. The unique viscosity solution to such an equation is a distance map, whose computation has numerous applications [START_REF] Sethian | Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry[END_REF] in domains as varied as motion planning, seismic traveltime tomography [START_REF] Bouteiller | An accurate discontinuous Galerkin method for solving point-source Eikonal equation in 2-D heterogeneous anisotropic media[END_REF], image processing [START_REF] Benmansour | Tubular structure segmentation based on minimal path method and anisotropic enhancement[END_REF], . . . The construction studied in this paper is designed is to achieve a geometrical property -strict acuteness with respect to a given asymmetric norm -ensuring that the resulting numerical scheme is strictly causal [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF][START_REF] Sethian | Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms[END_REF][START_REF] Alton | An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations[END_REF][START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF][START_REF] Mirebeau | Anisotropic Fast-Marching on cartesian grids using Lattice Basis Reduction[END_REF]. This in turn enables efficient algorithms for solving the numerical scheme, in a single pass over the domain, with linear complexity, and possibly in parallel [Tsi95,[START_REF] Rasch | Remarks on the O(N ) implementation of the fast marching method[END_REF]. In order to better focus on the problem of interest, further discussion of the addressed PDE and of its discretization is postponed to §A.

We study in this paper a one dimensional approximation-like problem, involved in the construction of local stencils of minimal cardinality for a numerical solver of eikonal PDEs, see Definition 1.3 for a formal statement. The efficiency of the procedure is directly tied to the complexity of the numerical scheme. A few properties of this problem deviate from the common settings in approximation theory, and deserve to be discussed here.

• The main function ϕ F : R →] -π/2, π/2[ considered benefits from regularity and integrability properties, derived from its geometrical interpretation §2.2. However these are fairly uncommon: -ϕ F is one-sided Lipschitz, and tan(ϕ F ) is bounded in the L 1 ([0, 2π]) norm.

• The approximation-like problem involves an interval subdivision procedure, that is reminiscent of e.g. dyadic splitting in non-linear approximation based on the Haar system [START_REF] Devore | Nonlinear approximation[END_REF]. However, subdivision is here governed by the Stern-Brocot tree, and breaks the interval [0, 2π] into unequal parts whose endpoints have rational tangents, see §3.

• We present a uniform "worst case" complexity result, but also an "average case" result under random shifts, see Theorem 1.4. Because of the peculiarities of the approximation procedure, a more favorable estimate is obtained in the average case.

In the rest of this introduction, we introduce the notations and concepts necessary to state our main result. Our first step is to equip the Euclidean space R 2 with the anisotropic geometry defined by a (possibly) asymmetric norm. Here and below, all asymmetric norms are on R 2 . Definition 1.1. An asymmetric norm is a function F : R 2 → R + which is 1-positively homogeneous, obeys the triangular inequality, and vanishes only at the origin:

F (λu) = λF (u), F (u + v) ≤ F (u) + F (v), F (u) = 0 ⇔ u = 0, for all u, v ∈ R 2 , λ ≥ 0. The anisotropy ratio of F is defined as µ(F ) := max |u|=|v|=1 F (u) F (v) .
Note that an asymmetric norm is always a continuous and convex function. We denote by

(u, v) ∈ [0, π] the unoriented Euclidean angle between two vectors u, v ∈ R 2 \ {0}, which is characterized by the identity cos (u, v) = u, v u v .
The next definition introduces a generalized measure of angle, associated with an asymmetric norm. We only consider acute angles, since obtuse angles will not be needed, and because their definition raises issues. The notion of F -acute angle is similarly defined in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]Vla08], but the related angular measure is new.

Definition 1.2. Let F be an asymmetric norm, which is differentiable except at the origin, and let u, v ∈ R 2 \ {0}. We say that u, v form an F -acute angle iff ∇F (u), v ≥ 0. We define the

F -angle F (u, v) ∈ [0, π/2] ∪ {∞} by cos F (u, v) := ∇F (u), v /F (v) (1)
if u, v form an F -acute angle. Otherwise we let F (u, v) := +∞.

We show in Lemma 2.3 that the r.h.s. of (1) is at most 1, so that F (u, v) is well defined, with equality if u = v, so that F (u, u) = 0. If F is the Euclidean norm, then one easily checks that the F -angle coincides with the usual Euclidean angle, when the latter is acute. More generally, if F (u) = Au for some invertible linear map A, then F (u, v) = (Au, Av), when the latter is acute. In general however, one has F (u, v) = F (v, u), and F -acuteness is not symmetric relation. The differentiability assumption in Definition 1.2 can be removed, see Definition 2.1.

The following definition introduces (F, α)-acute stencils, which are at the foundation of our numerical scheme, see Figure page 18. Their cardinality is directly proportional to the algorithmic complexity of our eikonal PDE solver, see §A, hence it is important to choose them as small as possible. When α = π/2 on recovers the F -acute stencils of [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF], and closely related concepts are considered in [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF][START_REF] Sethian | Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms[END_REF]Vla08,[START_REF] Alton | An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations[END_REF].

Definition 1.3. A stencil is a finite sequence of pairwise distinct vectors u 1 , • • • , u n ∈ Z 2 , n ≥ 4, such that det(u, v) = 1, u, v ≥ 0, for all u = u i , v = u i+1 , 1 ≤ i ≤ n, with the convention u n+1 := u n . It is said (F, α)-acute,
where F is an asymmetric norm and α ∈]0, π/2], iff with the same notations one has

F (u, v) ≤ α, F (v, u) ≤ α. (2)
We let N (F, α) denote the minimal cardinality of an (F, α)-acute stencil.

We provide in §3.2 a simple and efficient algorithm, based on a recursive refinement procedure and which is effectively used in our numerical implementation, for producing an (F, α)-acute stencil of minimal cardinality N (F, α). A similar method appears in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF] when α = π/2. The main result of this paper is the following estimate of N (F, α), both in the worst case and in the average case over random rotations of the asymmetric norm F . The average case makes sense in view of our application to PDE discretizations §A, since the orientation of the grid can be set and modified arbitrarily.

Theorem 1.4. For any asymmetric norm F and any α ∈]0, π/2], one has

N (F, α) ≤ C µ α 2 ln ln µ α 2 , 2π 0 N (F • R θ , α) dθ ≤ C ln(µ) α 2 ln µ α 2 . ( 3
)
where µ = max{µ(F ), 12}, R θ denotes the rotation of angle θ ∈ R, and C is an absolute constant.

In the intended applications, one typically has µ(F ) 100; such pronounced anisotropies are often encountered in image processing methods [START_REF] Benmansour | Tubular structure segmentation based on minimal path method and anisotropic enhancement[END_REF][START_REF] Mirebeau | Anisotropic Fast-Marching on cartesian grids using Lattice Basis Reduction[END_REF]. This bound is large enough that the asymptotic behavior of (3) w.r.t. µ is meaningful to our use cases. In contrast, we do confess that it seems pointless to let α → 0 in our applications (typically we set α = π/3). If one fixes α 0 ∈]0, π/2] then

N (F, α 0 ) ≤ Cµ ln ln µ, 2π 0 N (F • R θ , α 0 ) dθ ≤ C ln 2 (µ). (4)
uniformly w.r.t. µ. This improves on [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF], whose arguments are limited to the case α 0 = π/2, and where the sub-optimal bounds µ ln(µ) (resp. ln 3 (µ)) are obtained for (4, left) (resp. right).

Outline. The notion of F -acute angle, see Definition 1.2, is described in more detail §2, where related tools are introduced. The Stern-Brocot tree, an arithmetic structure underlying concept of stencil in Definition 1.3, is discussed in §3. We conclude in §4 the proof of Theorem 1.4. Some context on the intended applications of the presented results is given in §A.

Anisotropic angle

This section is devoted to the study of the anisotropic measure of angle F (u, v) of Definition 1.2, where u, v ∈ R 2 \ {0} and F is an asymmetric norm. Some elementary comparison properties, with the Euclidean angle (u, v) or with another angle F (u, w), are presented §2.1. We prepare in §2.2 (resp. §2.3) the proof of the average case (resp. worst case) estimate of Theorem 1.4, by introducing a helper function ϕ F (resp. ψ ± F ) for which we show a L 1 ([0, 2π]) norm estimate and a comparison principle with F .

In the rest of this section, we fix an asymmetric norm F , assumed to be continuously differentiable on R 2 \ {0}. That is with the exception of the following definition and proposition, where we briefly consider the case of non-differentiable norms, and show that the smoothness assumption holds without loss of generality. Closely related arguments are found in Lemma 2.11 of [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF].

Definition 2.1 (Generalization of F (u, v) with no differentiability assumption). Let F be an asymmetric norm, and let u, v ∈ R 2 \{0}. We say that u, v form an F -acute angle iff F (u+δv) ≥ F (u) for all δ ≥ 0. In that case we let

α = F (u, v) ∈ [0, π/2] denote the smallest value such that F (u + δv) ≥ F (u) + δ cos(α)F (v), (5)
for all δ ≥ 0. If u, v do not form an F -acute angle, then we let

F (u, v) := ∞.
Proposition 2.2. Definitions 1.2 and 2.1 agree on differentiable norms. Also, if F n → F locally uniformly as n → ∞, where (F n ) n≥0 and F are asymmetric norms, and u, v ∈ R 2 \ {0}, then

F (u, v) ≤ lim inf n→∞ Fn (u, v). (6)
If Theorem 1.4 holds under the additional assumption F ∈ C 1 (R 2 \ {0}), then it does without it.

Proof. Under the assumptions of Definition 1.2 one has

F (u + δv) = F (u) + δ ∇F (u), v + o(δ)
by differentiability of F at u, and F (u + δv) ≥ F (u) + δ ∇F (u), v by convexity of F , for any δ ≥ 0 and any v ∈ R 2 \ {0}. Thus Definitions 2.1 and 1.2 agree. The lower semi-continuity property (6) follows from the fact that (5) is closed under uniform convergence. Therefore if a given stencil is (F n , α)-acute for all n ≥ 0, then it is also (F, α)-acute see Definition 1.3. Thus N (F, α) ≤ lim inf n→∞ N (F n , α), and likewise for the l.h.s. of (3, right). Finally, we observe that any asymmetric norm F is the locally uniform limit of a sequence of asymmetric norms

F n ∈ C ∞ (R 2 \ {0}), n ≥ 1, defined as F n (u) := R F (R θ u) ρ n (θ) dθ,
where ρ n (θ) := nρ(nθ), and the mollifier ρ is smooth, non-negative, compactly supported, and has unit integral. The statement regarding Theorem 1.4 follows, which concludes the proof.

Elementary comparison properties

This subsection is devoted to elementary comparisons between F (u, v) and the angle between other vectors, see Lemma 2.4, or the Euclidean angle (u, v), see Proposition 2.5, where u, v ∈ R 2 \ {0}. In addition, Lemma 2.3 below was announced and used in the introduction to show that F (u, v) is well defined, and that F (u, u) = 0. Throughout this subsection, F denotes a fixed asymmetric norm, assumed to be differentiable except at the origin.

Lemma 2.3. For any u, v ∈ R 2 , with u = 0, one has

∇F (u), u = F (u), ∇F (u), v ≤ F (v). (7)
Proof. Euler's identity for the 1-homogeneous function F yields (7, left), whereas the triangular inequality F (u + δv) ≤ F (u) + δF (v) for all δ ≥ 0 yields (7, right).

The next lemma shows that the F -angle is non-increasing when an angular sector is split.

Lemma 2.4. Let u, v form an F -acute angle, and let w := αu + βv for some α, β > 0. Then

max{ F (u, w), F (w, v)} ≤ F (u, v)
Proof. Assume w.l.o.g. that α = 1, and denote λ := cos F (u, v). By convexity of F one has

∇F (w), v = ∇F (u + βv), v = ∇F (u + βv) -∇F (u), v + ∇F (u), v ≥ 0 + λF (v).
On the other hand, one obtains noting that λ ∈ [0, 1] by assumption

∇F (u), w = ∇F (u), u+βv ≥ F (u)+λβF (v) ≥ λ(F (u)+βF (v)) ≥ λF (u+βv) = λF (w).
The last proposition of this subsection is an upper bound on the F -angle in terms of the Euclidean angle and of the anisotropy ratio µ(F ) of the asymmetric norm. This upper bound grows non-linearly and perhaps more quickly than one may expect, namely as the square root of the Euclidean angle, because we do not make any quantitative assumption on the smoothness of F . Here and below we denote

u ⊥ := (-b, a) for any u = (a, b) ∈ R 2 . Proposition 2.5. For any u, v ∈ R 2 \ {0}, one has assuming µ(F ) (u, v) ≤ 1/2 F (u, v) ≤ 5µ(F ) (u, v). (8)
Proof. Denote θ := (u, v), α := F (u, v), and

µ := µ(F ). Assume w.l.o.g. that v = u + tan(θ)u ⊥ . Then ∇F (u), v = ∇F (u), u + tan(θ) ∇F (u), u ⊥ ≥ F (u) -tan(θ)F (-u ⊥ ). F (v) = F (u + tan θu ⊥ ) ≤ F (u) + tan(θ)F (u ⊥ ).
Observing that F (u ⊥ ) ≤ µF (u) and F (-u ⊥ ) ≤ µF (u), we obtain

1 -µ tan θ 1 + µ tan θ ≤ F (u) -F (-u ⊥ ) tan θ F (u) + F (u ⊥ ) tan θ ≤ ∇F (u), v F (v) = cos α = 1 -tan 2 (α/2) 1 + tan 2 (α/2) . (9)
This implies tan 2 (α/2) ≤ µ tan θ. We conclude the proof of (8) observing that tan(α/2) ≥ α/2, and tan θ ≤ (5/4)θ, both estimates by convexity of tan on [0, π/2[ and since θ ≤ 1/2. Note also that µ tan θ ≤ (5/4)µθ ≤ 5/8 < 1 by assumption, which shows that the l.h.s. of (9) is positive, and thus excludes the case where

F (u, v) = ∞, see Definition 1.2.

Gradient deviation

We describe and study a function ϕ F attached to the asymmetric norm F of interest, introduced in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF] and used in the proof of the average case estimate in Theorem 1.4. More precisely, the quantity ϕ F (u) is oriented Euclidean angle between a given vector u ∈ R 2 \ {0} and the gradient ∇F (u). Note that these two vectors are aligned if F is proportional to the Euclidean norm. The main results of this section are an L 1 estimate of ϕ F , see Lemma 2.9, and a comparison with the F -angle, see Proposition 2.10.

Definition 2.6. For each u ∈ R 2 \ {0}, define a signed angle ϕ F (u) ∈] -π/2, π/2[ by u ⊥ , ∇F (u) = F (u) tan ϕ F (u). ( 10
)
For θ ∈ R, we abusively denote ϕ F (θ) := ϕ F ( (cos θ, sin θ) ).

The next lemma shows, as announced, that |ϕ F (u)| is the Euclidean angle between the given vector u and its image by the gradient of F , and establishes a uniform upper bound for ϕ F .

Lemma 2.7. For any u ∈ R 2 \ {0}, one has

|ϕ F (u)| = (u, ∇F (u)), | tan ϕ F (u)| ≤ µ(F ). (11)
Proof. Equality (11, left) follows from Euler's identity (7, left) and the definition (10). Estimate (11, right) follows from -F (-u ⊥ ) ≤ u ⊥ , ∇F (u) ≤ F (u ⊥ ) see (7, right), and from the upper bound F (±u ⊥ ) ≤ µ(F )F (u) which holds by Definition 1.1 of the anisotropy ratio.

We recall in the next proposition, without proof, two key properties of the function ϕ F established in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]: a one-sided regularity property, and an upper bound on the integral of tan(ϕ F ) on any interval. See the plots of ϕ F on Figure page 18. Proposition 2.8 (Proposition 3.6 in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]). The function ϕ F : R →] -π/2, π/2[ obeys:

• (Regularity) For all θ ∈ R, one has ϕ F (θ) ≥ -1. • (Integral bound) One has | θ * θ * tan ϕ F (θ) dθ| ≤ ln µ(F ) for all θ * , θ * ∈ R.
Combining the one-sided regularity property and the integral bound, one obtains an L 1 estimate of tan(ϕ F ), as shown in the next lemma, which turns out to be a key ingredient of the proof of the average case estimate (3, right), see §4.2.

Corollary 2.9 (L 1 estimate of tan ϕ F ). One has with C = 2π √ 3 2π 0 | tan ϕ F (θ)|dθ ≤ C(1 + ln µ(F )) (12)
Proof. In view of Proposition 2.8 (Integral bound), of the continuity of ϕ F , and of its 2πperiodicity, there exists α 0 ∈ R such that ϕ F (α 0 ) = 0. Then inductively for n ≥ 0 let

• β n be the smallest β ≥ α n such that |ϕ F (β)| = π/3, • α n+1 be the smallest α ≥ β n such that ϕ F (α) = 0.
The sequences (α n , β n ) n≥0 are well defined, thanks to the periodicity of ϕ F , except if |ϕ F | < π/3 uniformly, but in that case the announced result (12) clearly holds. The last result of this subsection can be regarded as a refinement of Proposition 2.5.

If ϕ F (β n ) = π/3 for some n ≥ 0 then α n+1 -β n ≥ π/3, whereas if ϕ F (β n ) = -π/3 one has β n -α n ≥ π/3, by Proposition 2.8 (Regularity). Therefore α n+1 -α n ≥ π/3 for all n ≥ 0, thus α 6 ≥ α 0 + 2π, which implies 2π 0 | tan ϕ F (θ)| dθ ≤ 2π 0 tan(π/3) dθ + 6 ln µ(F ) ≤ 2π √ 3 + 6 ln µ(F ). (13
Proposition 2.10 (Estimate of F in terms of ϕ F ). Let u, v = 0 be such that (u, v) ≤ π/3. Then one has, with C = 32

min{ F (u, v), 2} 2 ≤ C (u, v) max{ (u, v), | tan ϕ F (u)|, | tan ϕ F (v)|, }. (14)
Proof. Denote θ := (u, v) and α := F (u, v). Assuming w.l.o.g. that u = v = 1 and det(u, v) > 0 one has

v = (u + u ⊥ tan θ) cos θ, and u = (v -v ⊥ tan θ) cos θ.
Using linearity in the first line, and convexity in the second line, we obtain

v, ∇F (u) = u + u ⊥ tan θ, ∇F (u) cos θ = F (u)(1 + tan ϕ F (u) tan θ) cos θ (15)
F (u) = F (v -v ⊥ tan θ) cos θ ≥ (F (v) -v ⊥ , ∇F (v) tan θ) cos θ = F (v)(1 -tan ϕ F (v) tan θ) cos θ Assume for a moment that -tan ϕ F (u) tan θ ≥ 1/2. Recalling that θ ≤ π/3, thus tan θ ≤ 2θ, we obtain -tan ϕ F (u)θ ≥ 1/4 and the announced result (14) is proved. Likewise if tan ϕ F (v) tan θ ≥ 1/2.
In particular, if α = +∞ then ∇F (u), v ≤ 0 by Definition 1.2, and therefore -tan ϕ F (u) tan θ ≥ 1 by (15), so that the result is proved.

In the following, we let t u := tan ϕ F (u), t v := tan ϕ F (v). Based on the previous argument we assume w.l.o.g. that t u tan θ ≥ -1/2, t v tan θ ≤ 1/2 and α = ∞. We obtain from ( 15)

cos α = v, ∇F (u) F (v) = v, ∇F (u) F (u) × F (u) F (v) ≥ (1 + t u tan θ)(1 -t v tan θ) cos 2 θ.
Taking logarithms yields with

t := max{0, -t u , t v } -ln cos α ≤ -2 ln(1 -t tan θ) -2 ln cos θ. (16)
An elementary function analysis shows that -ln cos α ≥ α 2 /2 for α ∈ [0, π/2[, and

-ln cos θ ≤ θ 2 for θ ∈ [0, π/3]. In addition tan θ ≤ 2θ for θ ∈ [0, π/3], and -ln(1 -x) ≤ 2x for x ∈ [0, 1/2].
Inserting these bounds in (16) yields the announced result α 2 /2 ≤ -ln cos α ≤ 4 max{-ln(1 -t tan θ), -ln cos θ} ≤ 4 max{4tθ, 2θ 2 }.

Regularized gradient deviation

We consider in this subsection two 1-Lipschitz regularizations ψ + F and ψ - F of the gradient deviation ϕ F . See the plots of ψ ± F on Figure page 18. Note that -ϕ F is already (but also only) one-sided 1-Lipschitz, see Proposition 2.8 (Regularity). We extend to ψ ± F some of the results of §2.2, namely the L 1 -norm estimate in Corollary 2.14 and the comparison with the F -angle in Proposition 2.10, which are used §4.1 in the proof of the worst case estimate in Theorem 1.4. We recall that ϕ F : R →] -π/2, π/2[ is 2π-periodic.

Definition 2.11. Define for any θ ∈ R

ψ + F (θ) := max η≥0 ϕ F (θ + η) -η, ψ - F (θ) := min η≥0 ϕ F (θ -η) + η. (17)
The functions ψ - F and ψ + F define an upper and lower envelope of ϕ F : for any θ ∈ R

-π/2 < inf R ϕ F ≤ ψ - F (θ) ≤ ϕ F (θ) ≤ ψ + F (θ) ≤ sup R ϕ F < π/2.
They play symmetrical roles, up to replacing ϕ F with θ → -ϕ F (-θ), which amounts to reversing the orientation of the plane R 2 . Hence results established for ψ + F automatically extend to ψ - F .

Lemma 2.12. The map ψ + F : R →] -π/2, π/2[ is 1-Lipschitz.

Proof. By design (17, left) the function ψ + F is one-sided 1-Lipschitz: for all θ ∈ R, h ≥ 0

ψ + F (θ + h) = sup η≥h ϕ F (θ + η) -(η -h) ≤ ψ + F (θ) + h.
On the other hand one has ψ + F (θ -h) ≤ ψ + F (θ) + h, for all h ≥ 0, as follows from the same property of the function ϕ F , see Proposition 2.8 (Regularity). Combining these two estimates, we obtain ψ + F (θ + h) ≤ ψ + F (θ) + |h|, for all θ ∈ R and all h ∈ R (positive or negative), hence ψ + F is 1-Lipschitz as announced.

The next lemma and corollary are devoted to estimating the L 1 ([0, 2π]) norm of ψ + F . We denote by |A| the Lebesgue measure of a measurable set A ⊆ R.

Lemma 2.13. Let θ 0 , θ 1 ∈ R be such that ψ + F (θ 0 ) = ψ + F (θ 1 ). Then |{θ ∈ [θ 0 , θ 1 ]; ψ + F (θ) > ϕ F (θ)}| ≤ |{θ ∈ [θ 0 , θ 1 ]; ψ + F (θ) = ϕ F (θ)}|. (18)
Proof. Denote by A 0 (resp. A 1 ) the set appearing in (18, left) (resp. (18, right)). Then

0 = ψ + F (θ 1 ) -ψ + F (θ 0 ) = θ 1 θ 0 d dθ ψ + F = A 0 d dθ ψ + F + A 1 d dθ ψ + F ≥ |A 0 | -|A 1 |,
where we used the observation that d dθ ψ + F (θ) = 1 for all θ ∈ A 0 , whereas d dθ ψ + F (θ) ≥ -1 for a.e. θ ∈ A 1 . The result follows.

Corollary 2.14 (L 1 estimate of ψ + F ). 2π 0 max{0, tan ψ + F -1} ≤ 2 2π 0 max{0, tan ϕ F -1} Proof.
As observed in Corollary 2.9 there exists θ 0 ∈ R such that ϕ F (θ 0 ) = 0. Thus ϕ F (θ) ≤ π/4 for all θ ∈ [θ 0 -π/4, θ 0 ], and therefore ψ + F (θ 0 -π/4) ≤ π/4. As a result, the level sets

Ψ(λ) := {θ ∈ R; ψ + F (θ) > λ}, Φ (
F -1} = π/2 π/4 | Ψ(λ)| tan λ dλ ≤ 2 π/2 π/4 | Φ(λ)| tan λ dλ = 2 2π 0 max{0, tan ϕ F -1}
From Corollaries 2.9 and 2.14 we obtain

2π 0 max{1, tan ψ + F } ≤ C ln µ, (19)
where µ := max{2, µ(F )} and C is an absolute constant. The same result holds for max{1, -tan ψ - F }, by a similar argument, see the comment after Definition 2.11. Finally, we compare the F -angle of two vectors with such integral quantities.

Proposition 2.15 (Estimate of F in terms of ψ ± F ). Let u, v ∈ R 2 \ {0}, with (u, v) ≤ π/3. Let Θ ⊆ R be a corresponding angular sector, with |Θ| = (u, v). Then min{ F (u, v), 2} 2 ≤ C Θ max{1, tan ψ + F , -tan ψ - F }, (20)
where C = 4C and C is from Proposition 2.10.

Proof. By angular sector, we mean that up to exchanging u and v one has Θ = [θ u , θ v [ where u (resp. v) is positively proportional to (cos θ u , sin θ u ) (resp. (cos θ v , sin θ v )). By Proposition 2.10 one has

F (u, v) 2 ≤ C max{|Θ| 2 , |Θ| | tan ϕ F (θ u )|, |Θ|| tan ϕ F (θ v )|}. If F (u, v) 2 ≤ C|Θ| 2 then the announced result (20) is proved, since |Θ| ≤ π/3. Otherwise we may assume w.l.o.g that F (u, v) 2 ≤ |Θ| | tan ϕ F (θ u )|. Denoting ψ F := max{ψ + F , -ψ - F } one has ψ F (θ u + h) ≥ ϕ * -h for all h ≥ 0, where ϕ * := |ϕ F (θ u )|.
We conclude by case elimination: 20) holds as announced.

• If ϕ * ≤ π/3, then F (u, v) 2 ≤ |Θ| tan(π/3), hence (
• Otherwise if ϕ * + (u, v) ≥ π/2, we obtain Θ | tan ψ F | ≥ π 2 -ϕ * 0 tan(ϕ * -h) dh = ln sin(2ϕ * ) cos ϕ * = ln(2 sin ϕ * ) ≥ ln(2 sin(π/3)) = ln 3 2 .
Thus the r.h.s. of ( 20) is bounded below by C ln(3)/2 ≥ 2 2 , hence (20) holds as announced.

• Otherwise if ϕ * + (u, v) ≤ π/2, then we obtain for all θ ∈ Θ tan ψ F (θ) ≥ tan(ϕ * -(π/2 -ϕ * )) = -cot(2ϕ * ) = 1 2 (tan ϕ * -cot ϕ * ) ≥ 1 4 tan ϕ * ,
using that ϕ * ≥ π/3 in the last inequality. Therefore Θ tan ψ F ≥ 1 4 |Θ| tan(ϕ * ), which implies (20) and concludes the proof.

The Stern-Brocot tree

We describe a variant of the Stern-Brocot tree [START_REF] Niqui | Exact arithmetic on the Stern-Brocot tree[END_REF], an arithmetic structure which allows to effectively construct and study the minimal (F, α)-acute stencil considered in Definition 1.3. We formally introduce the Stern-Brocot tree in this introduction, and then we relate it in §3.2 with the stencils of Definition 1.3. We estimate in §3.3 the cardinality of a subtree, based on the number of its inner leaves and on a measure of their depth, for use in the proof §4.1 of the worst case estimate of Theorem 1.4.

Let Z collect all elements of Z 2 whose coordinates are co-prime, and T all elements of Z 2 with unit determinant and a non-negative scalar product.

Z := {(a, b) ∈ Z 2 \ {0}; gcd(a, b) = 1}, T := {(u, v) ∈ Z 2 ; u, v ≥ 0, det(u, v) = 1}.
We often denote T = (u, v) the elements of the set T .

Definition 3.1. For any T = (u, v) ∈ T , we refer to T = (u, u+v) ∈ T and T = (u+v, v) ∈ T as its children, and we denote this relation by T T and T T . We also let

S(T ) = u, v , ∆(T ) = min{ u 2 , v 2 }.
By construction one has for any T T ∈ T

S(T ) ≥ 0, ∆(T ) ≥ 1, S(T ) ≥ S(T ) + ∆(T ), ∆(T ) ≥ ∆(T ). (21) Definition 3.2. A chain in T is a finite sequence T 0 • • • T n ,
where n ≥ 0. We write T * T * iff there exists a chain

T * = T 0 • • • T n = T * in T for some n ≥ 0.
The next lemma fully describes the graph (T , ). For that purpose, denoting by (e 1 , e 2 ) the canonical basis of R 2 we let T 0 := {(e 1 , e 2 ), (e 2 , -e 1 ), (-e 1 , -e 2 ), (-e 2 , e 1 )}.

Lemma 3.3 (Lemma 2.3 in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]).

• Let T = (u, v) ∈ T . The following are equivalent: (i) T ∈ T 0 , (ii) u = v , (iii) S(T ) < ∆(T ), (iv) T has no parent.

• The graph (T , ) is the disjoint union of four complete infinite binary trees, whose roots lie in T 0 .

The tree rooted in (e 1 , e 2 ) is isomorphic to the classical Stern-Brocot tree [START_REF] Niqui | Exact arithmetic on the Stern-Brocot tree[END_REF], an infinite binary tree labeled with rationals, via the mapping (u, v) → p/q where (p, q) = u + v. Each positive rational appears exactly once as a label, in its irreducible form, as follows from the first statement of the next proposition. See also [START_REF] Niqui | Exact arithmetic on the Stern-Brocot tree[END_REF].

Proposition 3.4. For each u ∈ Z with u > 1, there exists a unique (u -, u + ) ∈ T such that u = u -+ u + . By convention we let (u -, u + ) := (-u ⊥ , u ⊥ ) if u = 1. For any u, v ∈ Z (u, v) ∈ T ⇔ ∃k ≥ 0, v = u + + ku, (v, u) ∈ T ⇔ ∃k ≥ 0, v = u -+ ku.
Furthermore, u ± +ku > k u for all k ≥ 0. Also, u ± ≤ u with equality iff u = u ± = 1.

Proof. See Proposition 1.2 in [START_REF] Mirebeau | Adaptive, anisotropic and hierarchical cones of discrete convex functions[END_REF] for the existence and uniqueness of (u -, u + ).

The announced properties are obvious if u = 1, hence w.l.o.g. we assume u > 1. One has u 2 = u + 2 + 2 u + , u -+ u - 2 ≥ u + 2 + 0 + 1, hence u > u + as announced, and likewise for u -. One has u + + ku 2 = k 2 u 2 + 2k u, u + + u + 2 ≥ k 2 u 2 + 0 + 1 for all k ≥ 0, hence u + + ku > k u and likewise for u -as announced.

If (u, v) ∈ T , then det(u, v) = det(u, u + ), hence v = u + + ku for some k ∈ R. Since u + , v have integer coordinates, and u has co-prime coordinates, one has k ∈ Z. By definition 0 ≤ u, v = u, u + + k u 2 < (k + 1) u 2 , showing that k ≥ 0 as announced. Likewise for u -, and the reverse implication is obvious.

Angular partitions

To each element T = (u, v) of (our variant of) the Stern-Brocot tree one can associate an angular sector, whose width and covering properties are the object of this short subsection. Lemma 3.5. For all (u, v) ∈ T one has

( u v ) -1 ≤ (u, v) ≤ π 2 ( u v ) -1 .
Proof. One has sin( (u, v)) = det(u, v)/( u v ) = ( u v ) -1 . Also, by concavity, one has • A sub-forest is a set T * ⊆ T which contains the parent, if any, of each of its elements: for all T T with T ∈ T * one has T ∈ T * .

• An outer leaf of T * is an element of T \ T * whose parent, if any, lies in T * . An inner leaf of T * is an element of T * shows two children lie outside T * . Their sets are respectively denoted

L o (T * ) ⊆ T \ T * L i (T * ) ⊆ T * .
Said otherwise, an element T ∈ T \ T * (resp. T ∈ T * ) is an outer leaf (resp. inner leaf) of a sub-forest T * ⊆ T , iff T * ∪ {T } (resp. T * \ {T }) also is a sub-forest. In addition one easily checks that the angular sectors associated with the outer leaves define a partition of the angular space [0, 2π[, and that the angular sectors associated with the inner leaves are pairwise disjoint:

T ∈L o (T * ) Θ(T ) = [0, 2π[, T ∈L i (T * ) Θ(T ) ⊆ [0, 2π[. ( 22
)

Stencil construction

We show in Proposition 3.8 that stencils are in one to one correspondance with finite sub-forests of T , see Definitions 1.3 and 3.7. This yields an efficient construction of stencils with minimal cardinality, and a way of counting their elements, see Corollary 3.9.

Proposition 3.8. Let (u 1 , • • • , u n ), n ≥ 4, be a stencil in the sense of Definition 1.3, and let

L * := {(u i , u i+1 ); 1 ≤ i ≤ n}, (23)
collect the pairs of consecutive elements, with α n+1 := α n . Then L * is the set of outer leaves of some finite sub-forest T * ⊆ T , and in particular #L * = 4 + #T * . Any finite sub-forest T * of T can be obtained in this way.

Proof. We proceed by induction on the cardinality of L * . For initialization, we note that #L * ≥ 4, with equality iff L * = T 0 , in which case it collects the outer leaves of the empty sub-forest T * = ∅. Otherwise denote u = u i the element of L * with maximal norm, and observe that u i+1 = u + and u i-1 = u -by Proposition 3.4. Since L * T 0 one has u > 1, and therefore

(u i-1 , u i+1 ) = (u -, u + ) ∈ T , showing that (u 1 , • • • , u i-1 , u i+1 , • • • , u n ) is also a stencil in the sense of Definition 1.3. Thus by induction L * ∪ {(u i-1 , u i+1 )} \ {(u i-1 , u i ), (u i , u i+1 )} = L o (T * )
for some sub-forest T * of T , and therefore

L * = L o (T * ∪ {(u i-1 , u i+1 )}) as announced.
Conversely, we observed in (22) that the set of outer leaves of a finite sub-forest of T defines a partition the angular space, and thus yields a stencil.

Recall that a finite complete rooted binary tree has one more outer leaf than inner nodes. Since T * collects the inner nodes (possibly none) of four such trees, and L * their leaves, one has #L * = 4 + #T * as announced.

Corollary 3.9. Let F be an asymmetric norm, and let α ∈]0, π/2]. Define

T (F, α) := {(u, v) ∈ T ; F (u, v) > α or F (v, u) > α}. ( 24
)
Then T (F, α) is a finite sub-forest of T , and N (F, α) = 4 + #T (F, α).

[Tsi95] J.N. The main result of this section is Proposition A.1 known as acuteness implies causality [START_REF] Sethian | Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms[END_REF]. It requires that the numerical method be based upon strictly acute stencils, in the sense of Definition 1.3 with α < π/2. Under this condition, one can compute an approximate travel time T h (x), at a given discretization point x ∈ Ω h where h is the grid scale, in terms of suitable neighbor values T h (x + hu i ) and T h (x + hu i+1 ) no greater than T h (x) -hε, where ε > 0 is uniform over the domain. As a result, T h can be efficiently computed in a single pass over the domain using the fast-marching algorithm, similar to Dijkstra's method on graphs, which deals with vertices in the order of increasing values of T h . In addition let us mention that uniform causality, a.k.a. ε > 0, is a stable property which is also satisfied by suitably small perturbations of the numerical scheme, such as those related to second order accuracy [START_REF] Sethian | Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry[END_REF] and to source factorization [START_REF] Luo | Fast sweeping methods for factored anisotropic eikonal equations: multiplicative and additive factors[END_REF].

Consider a bounded domain Ω ⊆ R 2 , equipped with a Finslerian metric F : Ω × R 2 , (x, u) → F x (u). In other words, F is a continuous mapping, and F x (•) is an asymmetric norm for each x ∈ Ω in the sense of Definition 1.1. The Finslerian distance from x to y ∈ Ω is defined as One is interested in the distance from the boundary, T (x) := min{d F (x, y); y ∈ ∂Ω} often referred to as the "escape time" from the domain, which under mild assumptions is the unique viscosity solution [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF] to the following (generalized) eikonal Partial Differential Equation (PDE), written in Bellman form:

inf u∈S 1 F x (u) + ∇T (x), u = 0, ∀x ∈ Ω, T (x) = 0, ∀x ∈ ∂Ω. ( 34
)
Note that the PDE remains equivalent if the unit circle S 1 is replaced with any curve enclosing the origin. In particular, we can consider the closed polygonal line defined by a stencil, see Definition 1.3, possibly depending on x ∈ Ω and denoted u 1 (x), • • • , u n(x) (x) where n(x) ≥ 4. In the following, the explicit dependency u i = u i (x) w.r.t. the base point x ∈ Ω is often omitted readability, and by convention u n(x)+1 := u 1 . Consider a grid scale h > 0, and introduce the sets Ω h := Ω ∩ hZ 2 and ∂Ω h := (R 2 \ Ω) ∩ hZ 2 devoted to the discretization of Ω and ∂Ω. Semi-Lagrangian numerical schemes for the eikonal equation mimick (34) as follows: find T h : hZ 2 → R such that (solid), π/3 (dashed), π/4 (dotted). Right: Function ϕ F (solid), ψ + F (dashed, above), ψ - F (dotted, below). Vertical bars correspond to the angles of the stencil points. equals 0 for all x ∈ Ω h , with again the boundary condition T h (x) = 0 for all x ∈ ∂Ω h . Proposition A.1 (Acuteness implies causality [START_REF] Sethian | Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms[END_REF]). Assume that u 1 (x), • • • , u n(x) (x) is an (F x , α)-acute stencil, where α ∈]0, π/2[. Assume also that (35) vanishes, and that the minimum is attained for some 1 ≤ i ≤ n(x) and s ∈]0, 1[. Then T h (x) ≥ h cos(α)F x (u i ) + T h (x + hu i ),

T h (x) ≥ h cos(α)F x (u i+1 ) + T h (x + hu i+1 ).

Proof. A standard analysis based on Lagrange's optimality conditions shows that

hA T ∇F x ((1 -s)u i + su i+1 ) + T h (x + hu i ) T h (x + hu i+1 ) = T h (x) 1 1 ,
where A is the matrix of columns u i and u i+1 , see the Appendix of [START_REF] Sethian | Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms[END_REF] or the Appendix of [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]. Considering this vector equality componentwise yields the announced result.

)

  On each interval [α n , β n ] ∩ [0, 2π] we used the upper bound |ϕ F (θ)| ≤ π/3, which holds by definition of β n . On each interval [β n , α n+1 ] ∩ [0, 2π] we used Proposition 2.8 (Integral bound) and the fact that ϕ F does not change sign, which holds by definition of α n+1 .

  λ) := {θ ∈ R; ϕ F (θ) > λ}, are strict subsets of R for any λ ≥ π/4. They are also 2π-periodic sets, and for that reason we denote Φ(λ) := Φ(λ) ∩ [0, 2π[ and Ψ(λ) := Ψ(λ) ∩ [0, 2π[. Applying Lemma 2.13 to the closure [θ 0 , θ 1 ] of each connected component of Ψ(λ), and using periodicity, we obtain | Ψ(λ) \ Φ(λ)| ≤ | Φ(λ)|. Thus | Ψ(λ)| ≤ 2| Φ(λ)|, and therefore, as announced 2π 0 max{0, tan ψ +

2

  π ϕ ≤ sin ϕ ≤ ϕ for all ϕ ∈ [0, π/2], hence t ≤ arcsin t ≤ π 2 t for all t ∈ [0, 1]. Definition 3.6. Given T = (u, v) ∈ T we let Θ(T ) := [θ u , θ v [, where u is positively proportional to (cos θ u , sin θ u ) and θ u ∈ [0, 2π[, and likewise for v and θ v ∈]0, 2π]. If T ∈ T 0 , then Θ(T ) = [kπ/2, (k + 1)π/2[ for some 0 ≤ k ≤ 3. By construction, Θ(T ) = Θ(T ) Θ(T ) if T and T are the children of T , where denotes the disjoint union. In addition |Θ(T )| = (u, v) for all T = (u, v) ∈ T . Definition 3.7.

0 F

 0 d F (x, y) := inf γ∈Γx→y 1 γ(t) (γ (t)) dt, Γ x→y := {γ ∈ Lip([0, 1], Ω); γ(0) = x, γ(1) = y}.

Figure 1 :

 1 Figure1: Left: Unit sphere {F = 1} of a norm F , which is asymmetric in the second and third row. The origin is marked with a point. Center: Minimal (F, α)-acute stencil for α = π/2 (solid), π/3 (dashed), π/4 (dotted). Right: Function ϕ F (solid), ψ + F (dashed, above), ψ - F (dotted, below). Vertical bars correspond to the angles of the stencil points.

  Tsitsiklis. Efficient algorithms for globally optimal trajectories. IEEE transactions on Automatic Control, 40(9):1528-1538, September 1995.We present an elementary introduction to numerical methods for the computation of generalized traveltimes and distance maps, focusing on single pass semi-Lagrangian methods [Tsi95, KS98, SV03, BR06, AM12, Mir14b, Mir14a], at the expense of alternative approaches such as[START_REF] Luo | Fast sweeping methods for factored anisotropic eikonal equations: multiplicative and additive factors[END_REF][START_REF] Bornemann | Finite-element Discretization of Static Hamilton-Jacobi Equations based on a Local Variational Principle[END_REF], which is the context underlying of the problem studied in this paper. An open source code implementing this method is available on the author's webpage github.com/Mirebeau.

	[Vla08]	Alexander Boris Vladimirsky. Label-setting methods for Multimode Stochastic
		Shortest Path problems on graphs. Mathematics of Operations Research, 33(4):821-
		838, 2008.
	A Semi-Lagrangian discretization of Finslerian eikonal equations

This work was partly supported by ANR research grant MAGA, ANR-16-CE40-0014

Proof. The set T (F, α) is a sub-forest of T by Lemma 2.4, and is finite by Proposition 2.5. Denote by L o (F, α) the collection of its outer leaves, and by u 1 , • • • , u n the corresponding stencil, see Proposition 3.8. One has (u i , u i+1 ) ∈ L o (F, α) ⊆ T \ T (F, α), for any 1 ≤ i ≤ n, implying the (F, α)-acuteness property (2) by definition of T (F, α). This implies the upper bound N (F, α) ≤ n = #L o (F, α) = 4 + #T (F, α).

Conversely, let u 1 , • • • , u n be an (F, α)-acute stencil with minimal cardinality, and let L * and T * be as in Proposition 3.8. By Lemma 2.4, and recalling Definition 3.2, all elements of the set E := {T ∈ T ; ∃T ∈ L * , T T } obey the acuteness condition (2), hence E ⊆ T \ T (F, α). On the other hand, one has E = T \ T * , hence T (F, α) ⊆ T * , which yields the lower bound #T (F, α) ≤ #T * = #L * -4 = N (F, α).

Thanks to the tree structure, the set T (F, α) can easily be computed in practice, as well as the corresponding minimal (F, α)-acute stencil, by e.g. depth first search as in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF].

Cardinality of a sub-forest

We estimate the cardinality of a sub-forest of T based on the number of inner leaves and on their depth as measured by the function S, see Corollary 3.13 and Definition 3.1. The proof is based on a decomposition of the sub-forest into a disjoint union of chains. We state, without proof, a lower bound on the depth of the last element of a chain, which immediate follows from (21).

and defined as follows:

• (Main loop, iteration variable: i the chain index) Choose an element

If this set is empty, then the algorithm ends.

• (Inner loop, iteration variable: k the chain element index) Consider the two children T , T of T i k . If both lie in T * , then define T i k+1 as the one minimizing S (any in case of tie). If only one lies in T * , then define it as T i k+1 . If none lies in T * then the inner loop ends. Lemma 3.12. With the notations and assumptions of Definition 3.11. The chains are disjoint and their number I is also the number of inner leaves of T * . Denote by (u i , v i ) = T i 0 , 1 ≤ i ≤ I, the first element of each chain. Then the vectors {u i ; 1 ≤ i ≤ I, u i < v i } are pairwise distinct, and likewise

Proof. Assume for contradiction that T i k = T j l for some 0 ≤ i < j ≤ I, k ≤ n i , l ≤ n j , where (i, j, k, l) is minimal for lexicographic ordering. By construction of the first element of each chain, one has l ≥ 1. One has k = 0, since otherwise T i k-1 = T j l-1 contradicting the minimality of (i, j, k, l). Thus S(T j 0 ) < S(T j l ) = S(T i 0 ), contradicting the definition of T i 0 . By construction, the chains exhaust T * , are disjoint as shown in the above paragraph, and each one ends at an inner leaf. Hence their number is the number of inner leaves, as announced.

Assume that (u, v i ) and (u, v j ) are the first element of the chains C i and C j , with u < min{ v i , v j } and i < j.

The two children of T = (u, u + +ru) are T = (u, u + +(r+1)u) and T = (u + +(r+1)u, u + +ru), and satisfy S(T ) -S(T ) = u + + (r -1)u, u + + (r + 1)u > 0 for all r ≥ 1. Hence T j 0 ∈ C i , by construction of C i , see the inner loop, which is a contradiction. The result follows.

Corollary 3.13. Let T * be a sub-forest of T . Then for some absolute constant C

Proof. Denote by I := #L i (T * ) the number of inner leaves, and s := max{S(T ); T ∈ T * } the depth of T * as measured by S. By Lemma 3.12, T * is the disjoint union of I chains, with n 1 , • • • , n i elements, and whose first element we denote (u 1 , v 1 ), • • • , (u I , v I ). By Lemma 3.10 one has

where (w n ) n≥1 is an enumeration of Z 2 \ {0} sorted by non-decreasing norm. In (25, r.h.s.) the constant 4 corresponds to the case u i = v i and thus to chains rooted in T 0 by Lemma 3.3. The sum comes from the cases u i < v i or u i > v i and from the injectivity property of Lemma 3.12. Observing that w I ≤ C √ I and using (26, left) below, we conclude the proof.

Complexity estimates

This section concludes the proof of Theorem 1.4, dealing with the worst case and average case complexity estimates in §4.1 and §4.2 respectively. Most of the material has been prepared in §2 and §3. The following elementary estimate serves in several occasions.

Lemma 4.1 (Lemma 2.7 in [START_REF] Mirebeau | Efficient fast marching with Finsler metrics[END_REF]). For all r ≥ 2, one has with C an absolute constant

Corollary 4.2. For any r ≥ 2, one has with C an absolute constant

Proof. We distinguish the cases u = v , u < v , and u > v . In the first case one has (u, v) ∈ T 0 , see Lemma 3.3, so that the contribution of these terms is 4. Otherwise, assuming w.l.o.g. that u < v , one has v = u + + ku for some k ≥ 1, see Proposition 3.4. Therefore v ≥ k u , thus k ≤ r/ u 2 , which is an upper bound for the number of possible choices of v for a given u. Eventually we conclude the proof using (26)

Worst case

We establish the upper bound on the cardinality N (F, α) of a minimal (F, α)-acute stencil, announced in Theorem 1.4. The asymmetric norm F and parameter α ∈]0, π/2] are fixed throughout this section.

Lemma 4.3. T (F, α) has at most C ln(µ)/α 2 inner leaves, each obeying S(T ) ≤ 5µ/α 2 , where µ := max{2, µ(F )} and C is an absolute constant.

Proof. The set T (F, α) is introduced in Corollary 3.9, and the quantity S(T ) in Definition 3.1. Denoting by L i (F, α) the set of inner leaves of T (F, α), see Definition 3.7, we obtain

We successively used (i) the inclusion L i (F, α) ⊆ T (F, α) and definition (24) of T (F, α), (ii) Proposition 2.15 and ( 22), (iii) the integral upper bound (19). The first announced point follows.

On the other hand, for each T = (u, v) ∈ T (F, α) one has by (24) and Proposition 2.5

and therefore since det(u, v) = 1

implying as announced that S(T ) := u, v ≤ 5µ/α 2 .

Corollary 4.4. #T (F, α) ≤ C µ α 2 ln( ln µ α 2 ), with µ := max{12, µ(F )} and C an absolute constant. Proof. The announced estimate immediately follows from Lemma 4.3 and Corollary 3.13. Note that ln µ α 2 ≥ ln(12) (π/2) 2 > 1.

Average case

Throughout this section, we denote by F an asymmetric norm, which is continuously differentiable except at the origin. In the following, χ ≥1 : R → {0, 1} denotes the indicator function of the set [1, ∞[. Recall that T (F, α) is a family of pairs (u, v) of vectors, playing symmetrical roles, see (24). Our first lemma breaks this symmetry, and lets u (or v) play a preferred role through the introduction of auxiliary sets Z σ (F, δ, u), for suitable δ ≥ 0, σ ∈ {+, -}.

Lemma 4.6. Let δ = α 2 /C, where C is from Proposition 2.10. Then T (F, α) is a subset of

Therefore for some absolute constant

. Then by Proposition 2.10, and recalling that u v (u, v) ≤ 1 see Lemma 3.5, we obtain

The announced inclusion of follows, implying the cardinality estimate by Corollary 4.2.

The next lemma estimates the cardinality of each Z σ (F, δ, u) individually. Recall that u ± is defined in Proposition 3.4. Lemma 4.7. For each u ∈ Z, σ ∈ {+, -}, δ > 0, one has Z σ (F, δ, u) = ∅ if u > µ(F )/δ, and else

Proof. From definition (28, right) we obtain v = u σ + ku for some k ≥ 0. One has u σ + ku ≥ max{ u σ , k u }, see Proposition 3.4, hence k ≤ (tan ϕ F (u))/(δ u 2 ) which accounts for the first contribution in (30). The second contribution corresponds to the case k = 0.

In view of (29) and towards the average case estimate of T (F • R θ ), where R θ denotes the rotation of angle θ ∈ [0, 2π], we consider the following integral. Let 0 < δ ≤ 1 be fixed.

where implicitly u ∈ Z in each of the sums. Recall that ϕ F is defined both on non-zero vectors and on reals, by taking the argument see Definition 2.6, and that on R it is 2π-periodic.

The first contribution of (31) is separable w.r.t. θ and u, hence can be bounded as follows:

where µ := max{2, µ(F )}. We used Corollary 2.9 to upper bound the integral w.r.t. θ, and Lemma 4.1 for the summation over u.

In contrast, the second contribution in (31) is non-separable, motivating the following lemma.