Matthieu Bellec

Ulrich Kuhl

Gilles Montambaux

Fabrice Mortessagne

Topological transition of Dirac points in a microwave experiment

Keywords: numbers: 42.70.Qs, 73.22.Pr, 71.20.-b, 03.65.Nk

By means of a microwave tight-binding analogue experiment of a graphene-like lattice, we observe a topological transition between a phase with a point-like band gap characteristic of massless Dirac fermions and a gapped phase. By applying a controlled anisotropy on the structure, we investigate the transition directly via density of states measurements. The wave function associated with each eigenvalue is mapped and reveals new states at the Dirac point, localized on the armchair edges. We find that with increasing anisotropy, these new states are more and more localized at the edges.

Introduction.-Recently discovered condensed matter systems, such as graphene [1] or topological insulators [2], constitute an ideal playground to investigate the physics of massless Dirac fermions until now restricted to high energy physics. Indeed, the relativistic spectrum emerges at the conical intersection points, the so-called Dirac points, in the low energy electronic dispersion relation. The large potential of technological applications [START_REF]For graphene, see a recent outlook[END_REF] depends crucially on the properties of these quasi-particles. The manipulation of the Dirac points by external parametersfrom creation to annihilation -have recently raised a strong interest both theoretically [4][5][6][7] and experimentally [8,9]. By controlling the anisotropy of a honeycomb lattice, one can in principle move the Dirac points up to a transition where they merge and annihilate each other. This is a topological transition since both Dirac points are characterized by opposite topological numbers (opposite Berry phases) which annihilate at the transition. If the anisotropy is increased further, a band-gap opens in the dispersion relation. This transition from a gapless (Dirac) phase to a gapped phase corresponds to a Lifshitz phase transition from a semi-metallic to an insulating phase [4][5][6][7]. The experimental investigation of this transition is difficult to perform with condensed matter systems, e. g. graphene under uniaxial strain [10] or quasi-two-dimensional organic conductors under pressure [11]. Artificial systems such as molecular graphene or ultracold atoms in optical lattices have been recently proposed to experimentally probe this topological transition [8,9]. While this effect has not been clearly observed with molecular graphene [9], Ref. [8] reports the observation, using momentum-resolved interband transitions, of Dirac points merging with a Fermi gas in an anisotropic honeycomb lattice without six-fold symmetry.

Alternatively, discrete photonic systems (e. g. photonic lattices or microwave cavities), with graphene-like structures, have been employed as condensed-matter analogues [12][13][14][15]. In microwave experiments, the tightbinding form of graphene's Hamiltonian [16] can be established by using a honeycomb lattice of evanescently coupled dielectric resonators [14,15]. Dirac points and signature of the linear dispersion relation have been observed [13][14][15].

In this Letter, we take advantage of the high versatility of our tight-binding microwave set-up to explore the topological phase transition. The anisotropy of the honeycomb lattice is controlled through the nearest-neighbor hopping parameters. We directly measure the density of states (DOS) and the wave function associated with each eigenvalue. We observe a transition between the Dirac phase and the gapped phase exactly for the expected value of the anisotropy parameter defined in a tight-binding description. This is the first direct DOS measurement of this topological transition. Moreover the experimental set-up allows a very fine manipulation of the edges and a control of edge states which is not yet possible in condensed matter systems. We show that the anisotropy generates new states, at the Dirac frequency ν D , localized along specific armchair edges. With increasing anisotropy, their extension into the bulk decreases.

Experimental microwave graphene analogue.-For our experiments, we use a set of 222 identical coupled dielectric cylindrical resonators (5 mm height, 8 mm diameter and a refractive index of 6), hereafter called discs, placed in between two metallic plates. We establish a twodimensional tight-binding regime where the electromagnetic field is mostly confined within the discs and spreads out evanescently. The experimental details are described in [14,15]. Via a movable loop-antenna, the reflected signal S 11 is measured over a given frequency range at the disc positions r using a vectorial network analyzer. The bare frequency ν 0 of an isolated disc (∼ 6.65 GHz in the set-up considered here) corresponds to the on-site energy appearing in the tight-binding Hamiltonian. The coupling parameter t exp between two adjacent discs depends on the disc separation d and can be described, as expected for a two-dimensional system, by a modified Bessel function K 0 (see Table . I). Thus, by changing the distance between discs, one can change, in a controllable manner, the inter-site couplings. For a lattice composed of many discs, the set-up allows for a direct access to the local density of states (LDOS) through the measured quantity S 11 [14,15]. The DOS is obtained by averaging over all positions r. Moreover, our set-up allows to visualize the wave function associated with each eigenfrequency [START_REF] Bellec | Mortessagne[END_REF].

Tight-binding description.-In order to interpret quantitatively our experimental results, we present a tightbinding model on an infinite hexagonal lattice with first, second and third nearest-neighbor couplings. The on-site "energy" is given by the bare frequency ν 0 . The hopping amplitudes (in units of frequency) between nearestneighbor sites are called t ′ along the y-axis and t along the other directions (respectively red and blue links on Fig. 1(a). The next (next) nearest-neighbor couplings are respectively denoted as t 2 and t 3 . The anisotropy of the lattice can be simply taken into account via the first nearest-neighbor coupling (i. e. t ′ ), higher-order terms +δ. α = 1.9545 GHz, γ = 0.3167 mm -1 and δ = 0.0049 GHz have been experimentally determined [START_REF] Bellec | Mortessagne[END_REF].

are assumed to be unchanged (i. e. t 2 = t ′ 2 and t 3 = t ′ 3 ). In the basis of the two inequivalent sites forming the elementary cell, the Hamiltonian can be written in the Bloch representation:

H TB = ν 0 + f 2 (k) f (k) + f 3 (k) f * (k) + f * 3 (k) ν 0 + f 2 (k) (1)
where f (resp. f 2 and f 3 ) is the first (resp. second and third) nearest-neighbor contribution: -Experimentally, we first realize a regular graphene lattice with an hexagonal shape which has only armchair boundaries in order to eliminate edge states [see inset Fig. 2(a)]. We gradually add an anisotropy by increasing the coupling t ′ exp along the y axis -i. e. by decreasing the separation d ′ between the discs along y (insets in Fig. 2). As detailed in the Tab. I, the anisotropy parameter β varies from 1 to 3.5. The DOS corresponding respectively to β = 1, 1.8, 3.5 are depicted in Fig. 2. For the regular graphene, for which d = d ′ = 15 mm, the non-symmetric band structure and the point-like gap at the Dirac frequency ν D are observed [Fig. 2(a)].

f (k) = -(t ′ + te ik•a1 + te ik•a2 ), respectively f 2 (k) = -2t 2 [cos k • a 1 + cos k • a 2 +cos k • (a 1 -a 2 )
Here, due to the finite size of the system, the expected linear behavior of the DOS near the Dirac point appears only as a dip in the histogram. Moreover, the two logarithmic singularities have their signature in this finite sample (Fig. 2). By adjusting the calculated DOS shown in Fig. 1(b) to the experimental one [START_REF] Bellec | Mortessagne[END_REF], the following values for the three tight-binding couplings parameters are obtained: t = 0.016 GHz, t 2 /t = -0.091 and t 3 /t = 0.071. This value of t is in agreement with the Bessel fit of the experimental coupling (see Tab. I). Fig. 2(b) and (c) show the evolution of the DOS when the lattice is compressed. For large values of β, a gap opens as expected but additional states appear around ν D . We will provide a description of these states, identified as edge states, in the last part of the Letter. For an inspection of the topological transition, we eliminate their contributions by averaging the signal over bulk sites only. In Fig. 3(a), we plot the measured DOS obtained for six different values of β using a white-blue colorscale. The dashed red line corresponds to the Dirac frequency and the gray zone is used here to improve the visualization of the band gap opening. These experimental results are successfully compared with the DOS calculated for the corresponding infinite systems [Fig. 3(b)]. We clearly distinguish the topological transition between a gapless phase and a gapped phase which occurs for β c = 1.8, as expected from the theoretical expression β c = 2 -3t 3 /t and the tight-binding parameters given above. Before the transition, the spectrum exhibits a point-like gap. At the transition, since the DOS close to the Dirac point is supposed to switch from a linear to a square root behavior [4,6], the number of states close to the Dirac point is expected to increase. Due to the finite size of the lattice, a small gap always exists, but a higher concentration of states at ν D is clearly seen which reveals the topological phase transition. Finally, above the transition a gap opens. The gap and the bandwidths linearly increase with β (respectively the gray zone and the dotted lines in Fig. 3).

Edge states.-We now focus on the states which appear at the Dirac frequency ν D for anisotropic lattices (see Fig. 2). The spatial distribution of these states is depicted in Fig. 4 where it appears clearly that they are indeed edge states, which may appear a priori surprising since armchair boundaries are not expected to support edge states [START_REF] Nakada | [END_REF]. Their structure will be carefully studied in a future work, but several remarks are of immediate interest in this Letter. (i) They appear only along the edges which are not parallel to the anisotropy axis. (ii) Their localization along the edge increases when β increases. (iii) Their existence is not related to the topological transition observed in Fig. 3: they appear as soon as β > 1. These features are in agreement with the prediction for the existence of armchair edge states in deformed structures [19]. Moreover, we find that (i) the intensity on one triangular sublattice stays zero, (ii) the intensity on the other sublattice decreases roughly as (1/β) 2r where r is the distance to the edge in units of the lattice parameter. A more extensive investigation of these states, as well as of the states along zig-zag and bearded edges in anisotropic structures is in progress.

Conclusion.-To conclude, we have exploited the high flexibility of a microwave two-dimensional analogue of strained graphene to experimentally demonstrate the ex-istence of a topological transition between a gapless phase and a gapped phase when the anisotropy increases. We have investigated the spectral properties of this structure by directly measuring the density of electromagnetic modes. An appropriate description of this system requires to take into account not only first but also next (next) nearest-neighbor couplings. The wave functions associated with the states appearing at the Dirac frequency are easily measurable with our set-up and they reveal the presence of edge states along the armchair edges. They become more and more localized along the edges as the anisotropy is increased. Finally, the versatility of the set-up allows to mimic many of the spectacular properties of graphene and to reveal many other physical phenomena such as the influence of pseudo-magnetic field and associated Landau levels induced by a specific strain in graphene-like lattices [20].

  FIG. 1. (Color online) Left panels: Schematics of the hexagonal lattices. a1 and a2 define the primitive cell of the Bravais lattice. t (blue intersite links) and t ′ (red ones, along y axis) correspond to the nearest-neighbor couplings. d and d ′ are the corresponding distances. An anisotropy is introduced along the y axis: t ′ increases when d ′ decreases. Right panels: Calculated density of states (DOS) for an infinite system with first, second and third nearest-neighbor couplings given in the text. The red dashed line is the Dirac frequency νD = ν0+3t2. The insets show the corresponding dispersion relation. (a)-(b) Regular honeycomb lattice, β = 1. The two Dirac points are distinguishable. (c)-(d) Compressed lattice at the topological transition, β = 1.8. The Dirac points merge. (e)-(f) β = 3.5, a band gap opens (gray zone).

FIG. 2 .

 2 FIG. 2. (Color online) Experimental DOS for (a) the regular graphene (β = 1), (b) and (c) anisotropic structures with β = 1.8 and β = 3.5 respectively. The dashed red lines indicate the Dirac frequency νD. The gray zone shows the band gap with edge states at νD.

  ] and f 3 (k) = -t 3 [e ik•(a1+a2) + e ik•(a1-a2) + e ik(a2-a1) ]. The frequency spectrum is given by ν(k) = ν 0 + f 2 (k) ± |f (k) + f 3 (k)| and consists of two bands touching at the Dirac frequency ν D = ν 0 + 3t 2 . The corresponding DOS are represented in Fig. 1 for different values of the anisotropy parameter β = t ′ /t. For β = 1, two Dirac cones exist in k-space at k = ±K D = ±(a * 1a * 2 )/3 where a * i are reciprocal lattice vectors. For larger β, the Dirac points moves along k x axis. A topological transition occurs at β c = 2 -3t 3 /t, where the two Dirac points coalesce [inset Fig. 1(d)]. With the values of the coupling parameters extracted from the experiments (see below), we find β c = 1.8. For β larger than this critical value, the condition ν(K D ) = ν D cannot be fulfilled: a gap opens [inset Fig. 1(f)]. As a consequence, the density of states is strongly affected. The typical linear relation at the vicinity of the Dirac point (red dashed line) observed for β = 1 [Fig. 1(b)] turns to a square root law at the transition [Fig. 1(d)] [4, 6]. Then a gap opens for β > β c [gray zone in Fig. 1(f)]. Note that next (next) nearest-neighbor couplings lead to (i) a lower value of β c for the transition (1.8 instead of 2 expected when only the first nearest-neighbor coupling is taken into account [4, 6]), (ii) an asymmetry of the bands, (iii) a slight shift of ν D towards lower frequency and (iv ) a displacement of the two logarithmic singularities. Topological transition and gap opening.

FIG. 3 .

 3 FIG. 3. (Color online) (a) Experimental DOS for β varying from 1 to 3.5. To remove edges states and highlight the band gap opening, the DOS have been averaged over bulk sites only. The arrows at β = 1, 1.8 and 3.5 indicate the DOS plotted respectively in Fig. 2(a), (b) and (c), where the average was performed over all sites. (b) Calculated DOS for β varying from 1 to 3.5 for an infinite system. The arrows at β = 1, 1.8 and 3.5 indicate the DOS plotted in Fig. 1(b), (d) and (f) respectively. In (a) and (b), the gray zone shows the band gap opening, the dotted lines denote the linear dependence of the band edges and the red dashed line indicates νD.

1 FIG. 4 .

 14 FIG. 4. (Color online) Experimental wave function distributions at the Dirac frequency νD (red dashed line in Fig. 3) for β ranging from 1.3 to 3.5.

TABLE I .

 I Experimental anisotropy parameter β = t ′ exp /texp. For the regular lattice (i. e. β = 1), d = 15 mm and texp = 0.016 GHz. The intersite distances d ′ and the corresponding nearest-neighbor coupling values βtexp are also indicated.

	d ′	βtexp a	β
	mm	GHz
	15.0	0.015	1
	13.9	0.020	1.3
	13.0	0.027	1.8
	12.6	0.030	2
	12.0	0.037	2.5
	11.0	0.053	3.5

a Obtained according to the Bessel fit texp(d) = α |K 0 (γd/2)| 2


J Dusserre
email: dusserre@cirad.mg

J.-M Douzet

F Ramahandry

M Sester

B Muller

J Rakotoarisoa

Identification of the main constraints for upland rice crop in direct-seeding mulch-based cropping systems under the high altitude conditions of the Madagascar highlands

In the Madagascar highlands, increasing demand for rice combined with increasing land pressure in the lowlands led to the development of upland rice. To tackle the sustainability problem of upland crop production systems, Centre de coopération internationale en recherche agronomique pour le développement (CIRAD, an international governmental organization) and TAFA (an NGO) have developed direct-seeding mulch-based cropping systems (DMC), which not only decrease soil erosion but also increase soil fertility. To understand the mechanisms underlying the performance of upland rice DMC, an experiment was set up in 2003. The yield components of upland rice were studied under high-altitudinal conditions during six rainy seasons from 2003/04 to 2008/09. Treatments compared were two soil management techniques: conventional tillage with removal of most of the crop residues, associated with plowing ('plowing'); and a no-till system with direct seeding under mulch made of crop residues ('no-till'). The rice yields obtained were often better from plowing than from notill, except in the last season. This difference was due to blast disease, which was significantly lower in no-till with low fertilization (best percentage of full grains and better weight of grain). The differences in yields obtained between no-till and plowing were mainly explained by problems of crop installation. The plant densities and plant growth were lower in no-till. This was particularly linked to slower root development in notill. Overall, the biomass production of rotations of rice seemed too low in the highland conditions (low temperature) for the no-till system to be successful in the early years (low soil protection and slower restructuring of the soil).

Introduction

In the Madagascar highlands (region of Vakinankaratra), increasing demand for rice combined with increasing land pressure in the lowland areas led to development of upland rice on the hills. In this fragile ecosystem, use of conventional tillage is not sustainable, partly because of erosion compromising both upland rice by washing away of upper soil horizon, and the lowland rice below by silting.

The direct-seeding mulch-based cropping systems (DMC), which have proved their worth (and undergone rapid expansion) in places such as South America, the USA, Canada and Asia [START_REF] Derpsch | Development and Current Status of No-till Adoption in the World[END_REF] in providing permanent protection of soil, have opened up new possibilities of sustainability for the upland rice systems.

NGO TAFA and Centre de coopération internationale en recherche agronomique pour le développement (CIRAD) have experimented with DMC for 15 years in Madagascar, particularly in the region of Vakinankaratra, to limit physical and chemical erosion of soil on hills [START_REF] Michellon | Cropping systems on permanent soil cover for Madagascar highlands[END_REF]. In DMC, the cover plants (live or dead) and the mulches of crop residues fulfill various roles: reducing erosion [START_REF] Scopel | Impacts des systèmes de culture en semis direct avec couverture végétale (SCV) sur la dynamique de l'eau, de l'azote minéral et du carbone du sol dans les Cerrados brésiliens[END_REF], reducing runoff [START_REF] Findeling | Modeling the effects of a partial residue mulch on runoff using a physically based approach[END_REF], reducing losses from direct evaporation [START_REF] Scopel | Impacts des systèmes de culture en semis direct avec couverture végétale (SCV) sur la dynamique de l'eau, de l'azote minéral et du carbone du sol dans les Cerrados brésiliens[END_REF] and levels rates of soil C and N by forming a surface horizon with high humus content with greater biological activity [START_REF] Azontonde | Dynamique de la matière organique et de l'azote dans le système mucuna-maïs sur un sol ferrallitique (Terres de Barre) au Sud Bénin[END_REF].

An experimental study was set up by the Unité de recherche en partenariat 'Systèmes de culture et riziculture durables' (URP-Scrid) in 2003 at Andranomanelatra in the highlands of Madagascar, to compare different tillage systems in the cold conditions of this region and to assess the potential performance of systems based on DMC and upland rice.

Materials and methods

The experiment was conducted at Andranomanelatra (19°47′ S, 47°06′ E, 1642 m elevation) in the Vakinankaratra region of the Madagascar highlands. The climate is tropical altitude with summer rainfall. According to the World Reference Base (IUSS Working Group WRB, 2006), the soil is classified as Ferralsol [START_REF] Razafimbelo | Effet de différents systèmes de culture à couverture végétale sur le stockage du carbone dans un sol argileux des Hautes Terres de Madagascar[END_REF]. Plots were arranged in a randomized block design with four replications. Treatments compared were two soil management techniques: conventional tillage with removal of most of the crop residues, associated with plowing (treatment 'plowing': PLO); and a no-tillage system with direct seeding under mulch made of crop residues (treatment 'no-tillage': DMC). Six to eight rice seeds (cultivar FOFIFA 161) were sown manually in hills at a spacing of 20 × 20 cm (25 hills per m 2 ). The rotation was rice (Oryza sativa) the first year, followed by common bean (Phaseolus vulgaris) the second year. Common bean was associated with (since 2007) or without (before 2007) maize (Zea mays). After the harvest of common bean, oat (Avena sativa) was sown. Each season, the two crops of the rotation, i.e. rice and common bean, were present in the experimentation. Two fertilizations were used: 'Fu' composed of cattle manure at 5 t/ha, and 'FM' composed of NPK (11% N, 22% P 2 O 5 , 16% K 2 O) at 300 kg/ha, dolomite (CaMg(CO 3 ) 2 ) at 500 kg/ha, and cattle manure at 5 t/ha and two top-dressings with urea (46% N) at 50 kg/ha applied after sowing. Weeds were controlled by hand weeding, and insect protection was provided (by imidacloprid [2.5 g Gaucho per kg seed]) at sowing.

Results

Climatic conditions

Climatic conditions (monthly mean temperature and rainfall) of the six seasons are presented (Fig. 1a and1b). Temperature restricts upland rice during the crop cycle, in terms of sum of accumulated temperature and crop duration. The average temperatures (daily average over 24 hours) at 1640 m altitude, reach 17°C in October, at the beginning of the sowing period, and are barely above 18°C during the reproductive stage. The amplitude of thermal day/night is high (10-16°). The minimum temperature is below 12°C (below 10°C in October) during The average annual rainfall over the 6 years was 1475 mm. December and January are the rainy months. Despite some variability in rainfall patterns (periods of drought or very rainy periods during cyclones like in January 2007), the rainfall is sufficient to ensure adequate water supply for the rainfed crop during the cycle (October-April). However, the often erratic beginning of the rainy season may prevent early establishment of the crop or at least make it difficult in some years. Hailstorms occur frequently in the highlands and can cause severe losses at harvest time.

Runoff and erosion

The advantage of DMC is its effects on reducing erosion and runoff. Data on runoff, in this experiment and other experiments with different slopes, showed much less runoff in DMC than in plowing, and a control of erosion -erosion can be very high with plowing. But, in these highlands conditions (rainfall, low temperature, radiation and evapotranspiration) upland crops can't improve water infiltration into the soil in DMC [START_REF] Muller | Réduction du ruissellement en semis-direct sur couverture végétale : quel intérêt hydrique pour les cultures sur les hautes terres de Madagascar[END_REF]. However, the small gains in water consumption in DMC may be useful in a dry year, especially when rooting is limited, or if the crop system is heavily fertilized, and also for the production of catch crops [START_REF] Muller | Réduction du ruissellement en semis-direct sur couverture végétale : quel intérêt hydrique pour les cultures sur les hautes terres de Madagascar[END_REF].

Evolution of upland rice yield

Figure 2 shows the evolution of upland rice yields for the six seasons, according to soil management and fertilization; the average yields varied from 0.7 to 4.7 t/ha. The rice yields obtained were consistently better in plowing than in DMC (especially in the 2005/06 season), except for the last season. The effect of fertilization on yield was slight, but the effect of mineral fertilization (FM) on yield was greater in plowing in the first year. The analysis of yield elaboration is done through yield components developed successively during the rice cycle (in reference of studies on wheat by [START_REF] Meynard | Pour mieux connaître les variétés de blé : analyser l'élaboration de leur rendement[END_REF][START_REF] Latiri-Souki | Elaboration du rendement du blé dur en conditions semi-arides en Tunisie : relations entre composantes du rendement sous différents régimes de nutrition azotée et hydrique[END_REF].1 The yield variations were largely explained by variations in the number of full grains produced per square meter (Fig. 3), which depend on the conditions of growth and development between emergence and flowering, and not by weight (stage of filling) of grains.

Grain sterility

In the absence of constraints, sterility of the variety FOFIFA 161 is about 10%. In the first season, values of about 20% grain sterility were explained by wind occurring during flowering, and, for the two last seasons, high grain sterility was explained by the passage of a cyclone at flowering in 2007/08, and the impact of blast disease on early grain filling in 2008/09 (Fig. 4). When it was first released, FOFIFA 161 was considered resistant to blast disease, but its sensitivity apparently increased over the years, and blast pressure is high in the highlands. Epidemiological studies on the incidence and severity of blast were made during 2008/09. These results correlated with the sterility of the grains. A linear relationship was obtained in data from the treatment plowing (R² = 0.7735; Fig. 5). Other epidemiological studies conducted in 2004/05 and 2005/06 on a highly blastsusceptible variety indicated differences between methods of soil management in terms of incidence and severity of the disease. In DMC, the incidence and severity of blast were lower than in plowing, and the dynamics of disease progression were delayed in DMC [START_REF] Sester | Cropping system to limit blast disease in rainfed rice[END_REF].

Stage from emergence to heading of rice crop

Looking specifically at the stage from emergence to heading (Fig. 6), the effect of fertilization was marked on the production of panicles per m². There was better production of panicles independent of soil management, Making the connection between the two first components of yield (number of panicles per m², and number of plants per m²), we can see the effects of treatments on the development of the number of grains, and obtain information on this stage from emergence to heading. A linear relationship (Fig. 7) was found between these two components, followed by a plateau. For all points on this relationship (especially 2004/05 FM and 2005/06), variations in the number of panicles per m² were explained by variations in the number of plants per m². In 2008/09, density of plants did not induce more panicles, as the number of panicles produced per plant was reduced by competition between plants. The effect of fertilization was marked: fewer panicles per plant, for similar densities of plants, were observed in Fu treatments (particularly in 2003/04, 2004/05, 2006/07 and 2008/09).

Comparing plowing and DMC in FM treatment closely (Fig. 8), we see that the differences between soil management for 2004/05 and 2005/06 were as a result of differences in plant densities, with lower values than Establishment of the crop is more difficult in DMC: no tillage slows root development, and more difficult weed control in DMC (especially in early years) can explain these differences.

However in 2008/09, the sixth year of cropping, a positive effect was observed in DMC on this stage of crop cycle compared to plowing.

First results in a separate root experiment (data not shown), showed greater and faster root development with soil plowing. Measurement at early flowering stage on other cropping systems (upland rice in rotation with intercropping of maize comparing plowing and DMC; upland rice in rotation with intercropping of maize and Brachiaria in DMC) showed greatest number of root impacts in plowing in the first 10 cm of soil, and greatest number of root impacts in DMC from 25 cm depth of soil (although differences were not statistically significant) [START_REF] Dusserre | Caractérisation du taux d'exploration racinaire du riz pluvial sous différentes modes de gestion du sol[END_REF]. A method for characterization of root system of upland rice has been developed (Dusserre et al., 2009b) and experimentation is underway to compare root development in plowing and DMC. The main hypothesis is slower rice development under DMC than under plowing. Confirming this hypothesis, durations between sowing and flowering were longer in DMC than in plowing in 2004/05 and especially 2005/06 (Fig. 9). The FM treatment in plowing always had the shortest duration. Thus, fertilization stimulates the establishment of the crop. Soil insects like scarab beetle larvae (white grub) cause reduction of number of plants/m², and can significantly damage upland rice. In this cropping system (upland rice in rotation with bean followed by oat), ratings of attack indicated no reduction in attacks in DMC over time, unlike other cropping systems observed (e.g. as rice in rotation with succession of oat, bean and ryegrass in DMC, where there is no need to treat the seeds after 4 years of cropping); in fact, attacks are greater under DMC [START_REF] Ratnadass | Dispositifs pour l'évaluation des impacts des systèmes de culture sur les dégâts des insectes terricoles sur le riz pluvial à Madagascar[END_REF].

Biomass production of crop rotation

Quantification of biomass produced on the rotations of rice (without grain) were measured for the first (oat straw) and the two last seasons (maize straw, bean residue and oat straw) (Fig. 10). To improve the total production of biomass, we added maize into the rotation in 2007/08. Non-grain biomass ranged from 5 to 6 t/ha in FM treatment. For comparison, on studies conducted in farmers' plots in a different ecology in Madagascar (altitude 700 m) where DMC is adopted, the biomass produced is in the order of 6.5-7.5 t/ha (Naudin, personal communication). The increase in biomass production of rice rotation could be a good way to improve DMC. More aerial biomass could contribute to better protection of the soil and more subterranean biomass could speed up improvement of and maintain good soil porosity through the biological activity of roots and soil organisms.

Conclusions

Long-term experimentation (six seasons: 2003/04 to 2008/09) allowed analyses of the performance of upland rice cropping systems.

The temperature conditions are very restrictive for the cultivation of upland rice in the highlands. The water conditions are not limiting in terms of amount available for the crop, but can have adverse effects (waterlogging, leaching) (not analyzed in this study).

The rice yield obtained was often better in plowing compared to DMC, except in the last season. The reversal in 2008/09 was due to blast disease at early grain-filling stage, which was higher in plowing than in DMC. The differences in yields obtained between DMC and plowing were mainly explained by problems during crop establishment. Plant density and plant growth were lower in DMC. This was particularly linked to slower root development in DMC.

Overall, the biomass production in crop rotation of rice seemed too low under the highland conditions (low temperature) for DMC to be successful in the early years (low soil protection and slower natural restructuration of the soil).

Diversified crop rotations or intercropping with plants with more efficient root systems are being tested. These plants may show other advantages such as being fodder plants (pigeon pea, finger millet, Stylosanthes, vetch, lupin) and/or having repellent properties against soil insects (forage radish, rattlepod Crotalaria sp.) (Dusserre et al., 2009a). However, these systems require more technical expertise for their implementation and may be inaccessible to farmers.

Figure 1a .

 1a Figure 1a. Maximum (T max), mean (T mean) and minimum (T min) monthly temperatures in six seasons

Figure 2 .

 2 Figure 2. Upland rice yields by soil management (PLO, plowing; DMC, no till) and fertilization (Fu, cattle manure; FM, cattle manure and fertilizer) in six seasons

  Ecological intensification and diversification of rice-based systems Dusserre et al.: Constraints to rice in Madagascar highlands 2.12.4 Second Africa Rice Congress, Bamako, Mali, 22-26 March 2010: Innovation and Partnerships to Realize Africa's Rice Potential

Figure 3 .Figure 4 .

 34 Figure 3. Relation between yield and number of full grains per m 2 at harvest, for all seasons and treatments

  Ecological intensification and diversification of rice-based systems Dusserre et al.: Constraints to rice in Madagascar highlands Second Africa Rice Congress, Bamako, Mali, 22-26 March 2010: Innovation and Partnerships to Realize Africa's Rice Potential 2.12.5 most clearly in the first and the last seasons. There was no effect of organic-matter fertilizer in DMC in 2004/05, 2005/06 and 2007/08 seasons, when plowing FM gave the most panicles per m². For the 2006/07 season, there is a weak effect of fertilization. Differences in yields for this season (2006/07), higher in plowing FM, were explained by a greater production of spikelets per panicle in plowing (data not shown).

Figure 5 .Figure 6 .

 56 Figure 5. Relation between percentage of grains affected by blast and percentage of grain sterility in the 2008/09 season

  Ecological intensification and diversification of rice-based systems Dusserre et al.: Constraints to rice in Madagascar highlands 2.12.6 Second Africa Rice Congress, Bamako, Mali, 22-26 March 2010: Innovation and Partnerships to Realize Africa's Rice Potential in the relationship for 2007/08 (i.e. we can see a difference in plant densities between plowing and DMC, on the same relationship for 2004/05 and 2005/06, but below the relationship for 2007/08; Fig. 8).

Figure 7 .Figure 8 .

 78 Figure 7. Relationship between number of panicles per m² and number of plants per m² at harvest for all seasons and fertilizations, independent of soil management (There are two data points per treatment as plowing and DMC are not specifically

  Ecological intensification and diversification of rice-based systems Dusserre et al.: Constraints to rice in Madagascar highlands Second Africa Rice Congress, Bamako, Mali, 22-26 March 2010: Innovation and Partnerships to Realize Africa's Rice Potential 2.12.7

Figure 9 .

 9 Figure 9. Number of days from sowing to flowering by soil management (PLO, plowing; DMC, no till) and fertilization (Fu, cattle manure; FM, cattle manure and fertilizer) in six seasons

  Ecological intensification and diversification of rice-based systems Dusserre et al.: Constraints to rice in Madagascar highlands 2.12.8 Second Africa Rice Congress, Bamako, Mali, 22-26 March 2010: Innovation and Partnerships to Realize Africa's Rice Potential

Figure 10 .

 10 Figure 10. Biomass production except grain of rice rotation (kg/ha) by soil management (PLO, plowing; DMC, no till) and fertilization (Fu, cattle manure; FM, cattle manure and fertilizer) in three seasons

In other words, yield is the product of its five components: no. plants/m2 × no. panicles/plant × no. grains/panicle × grain fertility × grain weight.


Isabelle Sivignon
email: isabelle.sivignon@gipsa-lab.grenoble-inp.fr

Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment

 for "short" segments.

Introduction

Digital Straight Lines (DSL) and Digital Straight Segments (DSS) have been known for many years to be interesting tools for digital curve and shape analysis. The applications range from simple coding to complex multiresolution analysis and geometric estimators. All these applications require to solve the so-called DSS recognition problem. Many algorithms, using arithmetics, combinatorics or dual-space have been proposed to solve this problem, reaching a computational complexity of O(n) for a DSS of length n. A DSS belongs to infinitely many DSL of different characteristics, only one DSL enables to define the minimal characteristics of a DSS. In [START_REF] Said | Multiscale discrete geometry[END_REF], the authors introduce the following problem: given a DSL of known characteristics and a subsegment of this DSL, compute the minimal characteristics of the DSS. The authors originally encountered this problem for implementing a fast algorithm to compute a multiresolution representation of a contour. This problem also arises for the digitization of a segment given by its two floating-point endpoints: indeed, the slope computed from the endpoints may be quite far from the minimal characteristics of the digitized segment, especially if the segment is short. Two algorithms (SmartDSS and ReversedSmartDSS) are presented in [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Said | Computing the characteristics of a subsegment of a digital straight line in logarithmic time[END_REF]: both use the decomposition into continuous fractions of the DSL slope and reach a logarithmic complexity.

This problem is however not so new since in [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF], the author presents a quick sketch of a method that solves it using the Farey Fan. The announced complexity of the method is O(log 2 n) for a segment of length n. In this paper, we investigate further in this direction to provide a thoroughly defined algorithm. Moreover, we show how its complexity can be lowered to O(log(n)) with an astute use of arithmetical properties of the Farey Fan. Finally, we compare the performance of our algorithm with the ones proposed in [START_REF] Said | Multiscale discrete geometry[END_REF] and [START_REF] Said | Computing the characteristics of a subsegment of a digital straight line in logarithmic time[END_REF] and show that it behaves particularly well for "short" segments.

2 Setting the problem 2.1 Digital line, segment and minimal characteristics [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. These DSL are 8-connected and often called naive. The slope of the DSL is the fraction a b and µ b is the shift at the origin. In the following, without loss of generality, we assume that 0 ≤ a ≤ b. The remainder of a DSL of characteristics (a, b, µ) for a given digital point (x, y) is the value axby + µ. The upper (resp. lower) leaning line of a DSL is the straight line ax-by +µ = 0 (resp. axby + µ = b -1). Upper (resp. lower) leaning points are the digital points of the DSL lying on the upper (resp. lower) leaning lines.

A Digital Straight Line (DSL for short) of integer characteristics (a, b, µ) is the infinite set of digital points (x, y) ∈ Z 2 such that 0 ≤ ax -by + µ < max(|a|, |b|) (gcd(a, b) = 1)
A Digital Straight Segment (DSS) is a finite 8-connected part of a DSL. It can be uniquely defined by the characteristics of a DSL containing it and two endpoints P and Q. However, a DSS belongs to an infinite number of DSLs. In this context, the minimal characteristics of a DSS are the characteristics of the DSL containing it with minimal b [START_REF] Sivignon | Digital intersections : carrier, connectiviy and periodicity properties[END_REF]. Note that the notions of leaning points and lines are similarly defined for DSSs. DSS recognition algorithms aim at computing the minimal characteristics of a DSS, taking profit of the following fact: (a, b, µ) are the minimal characteristics of a DSS if and only if the DSS contains at least three leaning points [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. In this case, the minimal characteristics are the characteristics of the DSS upper leaning line.

The set of DSLs containing a DSS is usually called the preimage of the DSS. Given a DSS S, it is defined as

P(S) = {(α, β), |α| ≤ 1 | ∀(x, y) ∈ S, 0 ≤ αx -y + β < 1}.
The preimage can be represented in the (α, β) space, where α represents the slope and β the shift at the origin of a straight line.

The preimage of a DSS is a polygon with a well-defined structure that is directly related to the leaning points and lines defined by its minimal characteristics [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF][START_REF] Dorst | Discrete representation of straight lines[END_REF]. Figure 1 below (from [START_REF] Coeurjolly | On digital plane preimage structure[END_REF]) illustrates this point.

Proposition 1 ([4]

). Let P(S) be the preimage of S. Let ABCD be the polygon defined by this preimage, where A is the upper left most vertex, and the vertices are named counterclockwise. Following the notations of Figure 1 we have: 3 ) maps to the upper leaning line, the characteristics of which are the minimal characteristics of the DSS.

• The vertex B maps to the upper leaning line U U ;

• The vertex D maps to the lower leaning line LL translated by the vector (0, 1) in the digital space;

• The vertex A maps to the straight line U L + , where L + = L + (0, 1);

• The vertex C maps to the straight line U L + , where L + = L + (0, 1).

The minimal characteristics of S are (a, b, µ) if and only if B = ( a b , µ b ) (p and q relatively prime). B is called the characteristic point of P(S). Edges [AB] and [BC] are called lower edges.

Farey fan

Definition 1 (Ray). Let x and y be two nonnegative integers. The ray defined by x and y is defined and denoted as follows:

R(x, y) = {(α, β)|β = -xα + y}
The slope of the ray is x.

Note that x is not the geometrical slope of the ray but its absolute value. In the following, the order on the slopes is to be understood as the order on the absolute values of the geometrical slopes.

Definition 2 (Farey Fan). The Farey Fan of order n, denoted by F n is defined in the (α, β) space as the arrangement of all the rays R(x, y) such that 0 ≤ y ≤ x ≤ n, and such that 0 ≤ α ≤ 1 and 0 ≤ β ≤ 1. A facet of F n is a cell of dimension 2 of this arrangement. In the following, a point of F n stands for any point v of the (α, β) space (0 ≤ α ≤ 1 and 0 ≤ β ≤ 1) belonging to a ray, and such that the abscissa of v is a fraction of denominator smaller than or equal to n.

For any n, it is well known that there is a bijection between the facets of F n and the set of DSSs of length n (composed of n + 1 pixels) [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF]. Definition 3. Let S be a DSS of length n. F acet(S) is the facet equal to P(S) in the Farey fan of order n.

Moreover, from Proposition 1, a one-to-one correspondence can be defined between a facet and the characteristic point of the facet. Definition 4. Let f be a facet of the Farey fan of order n. We denote by CP oint(f ) the point v of f such that, if v = ( p q , r q ), then (p, q, r) are the minimal characteristics of the DSS F acet -1 (CP oint -1 (v)).

The Farey Fan of order 6 is depicted in Figure 2(a). The characteristic points of a few facets are depicted. Note that three types of facets can be identified:

• quadrilateral facets (in orange in Figure 2(a));

• upper triangular facets (in green in Figure 2(a));

• lower triangular facets (in blue in Figure 2(a)).

Consider now the following problem:

Problem 1. Given a DSL L of characteristics (a , b , µ ) and two points P (x P , y P ) and

Q(x Q , y Q ) of this DSL, compute the minimal characteristics (a, b, µ) of the DSS S = {(x, y) ∈ L | x P ≤ x ≤ x Q }.
After a translation of the characteristics of L such that P is set to the origin (µ ← µ + ax P -by P ), this problem is equivalent to the following one:

Problem 2. Given a point Λ( a b , µ b ) and a point Q(x Q , y Q ), find the point v of the Farey fan of order n = x Q such that Λ ∈ CP oint -1 (v).
In other words, the problem is to find the characteristic point of the facet of

F n containing Λ.
All in all solving Problem 2 is equivalent to performing a point location in an arrangement of lines. However, the number of facets in the Farey fan of order n (which is equal to the number of DSS of length n) is in O(n 3 ) [9, 10, 2], and point location algorithms in such a structure are expensive in term of both time and space complexity [START_REF] Wein | CGAL -2D Arrangements[END_REF]. This brute force approach is then less efficient than classical DSS recognition algorithms [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Troesch | Interprétation géométrique de l'algorithme d'euclide et reconnaissance de segments[END_REF][START_REF] Kovalevsky | New definition and fast recognition of digital straight segments and arcs[END_REF][START_REF] Dorst | Discrete straight line segments: Parameters, primitives and properties[END_REF].

In the following sections, we revisit the approach proposed by [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF] and present an algorithm to solve Problem 2 in time complexity O(log n), without explicitly computing the Farey fan. In the next section, we recall several structural and arithmetical properties of the Farey fan, and derive some very useful corollaries. These properties are the core of the algorithm detailed in section 4.

Properties of the Farey Fan

The Farey series of order n is the set of irreducible fractions in [0, 1] of denominator lower than or equal to n [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. All the properties below are illustrated in Figure 2(b) in the Farey fan of order 6. The first three properties are from [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF] and the reader is invited to consult this reference for the proofs, that are fairly simple.

Property 1 ([12]

). The abscissas of intersections of a ray R(x, y) of F n with other rays are consecutive terms of a Farey series of order max(x, nx).

In Figure 2(b), the abscissas of the intersections between the ray R(2, 1), depicted in red, and the other rays of F 6 are consecutive terms of the Farey series of order 4 = max(2, 6 -2).

Property 2 ([12]

). Let f i and f i+1 be two consecutive fractions of the Farey series of order n. In the interval f i < α < f i+1 , there is no intersection of rays. Thus, in this interval the Farey fan is a simple ladder of rungs.

In Figure 2(b), two ladders are depicted in blue for f i = 1 3 and f i = 2 3 . Property 3 ([12]). Let v( p q , r q ), 0 ≤ p ≤ q ≤ n, be a point of F n . Let R(x 0 , y 0 ) be the ray of minimum slope passing through v. The other rays passing through v have a slope equal to x 0 + kq with k ∈ Z and x 0 + kq ≤ n.

In Figure 2(b), three rays go through the point ( 12 , 1 2 ) (in orange). The slopes of these rays are equal to x 0 = 1, 3 and 5. From this property, we can derive the following corollary.

Corollary 1. Let v( p q , r q ), 0 ≤ p ≤ q ≤ n, be a point of F n . Let R(x, y) be a ray passing through p. R is the ray of smallest slope passing through v if and only if xq < 0. It is the ray of greatest slope passing through v if and only if x + q > n.

Property 4. Let p q be a fraction of the Farey series of order n. The intersection between the line α = p q and F n is exactly the set of points ( p q , r q ) where r takes all the integer values between 0 and q.

Proof. We study the intersection between R(x, y) defined by the equation β = -αx + y and α = p q . We get β = -px+qy q . For 0 ≤ y ≤ x ≤ q ≤ n, the quantity -px + qy takes all the integral values in the interval [|0, q|], which ends the proof.

In Figure 2(b), the intersection between α = 4 5 (depicted in green) and F n is the set of points ( 45 , r 5 ) with r ∈ Z, 0 ≤ r ≤ 5. Using Properties 2 and 4, we can prove the following result to compute the ray of smallest slope in a given point.

Corollary 2. Let v( p q , r q ), 0 ≤ p ≤ q ≤ n, be a point of F n . Let p q be the fraction following p q in the Farey Series of order n. The ray of smallest slope passing through v is defined by the point v and the point of coordinates v ( p q , rq q q ).

Proof. From Property 2, F n is a ladder in the interval [ p q , p q ], which means there is no intersection of rays in this interval. From Property 4, we know that there is at least one ray passing through the point v. Again from Property 4, all the rays passing through v cut the line of equation α = p q in a point v ( p q , r q ), r ∈ Z, 0 ≤ r ≤ q . Among all these rays, the ray of smallest slope is the one that passes through the point v max ( p q , rmax q ) where r max is the maximal value of r such that r q ≤ r q . r max is given by rq q which ends the proof.

Fast walk in the Farey Fan

Following Problem 2, we look for the characteristic point of the facet of F(n) containing a given point Λ( a b , r b ). From Proposition 1, Section 2.2 and Property 4 we have the following characterization of the characteristic point. 1. either v is the intersection of the two lower edges:

(a) the ray supporting the right lower edge is the one of smallest slope in v;

(b) the ray supporting the left lower edge is the one of greatest slope in v;

2. or v is on the unique lower edge and more than one ray passes through the point ( pv qv , rv+1 qv )

As in [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF], the algorithm consists of three steps that are detailed in the following sections:

1. Find the ladder to which Λ belongs; 2. Locate the highest ray that lies on or below Λ: this ray supports a lower edge of the facet (Section 4.2, Algorithm 1);

3. Walk along the ray(s) to determine the characteristic point (Section 4.3, Algorithm 2).

Particular cases where Λ is a point of F n (either on a ray, or a vertex) are eluded, so that the focus is done on the general case. However, these particular cases are not complicated to handle.

Find the ladder

Given a point Λ( a b , µ b ), finding the ladder to which Λ belongs in F n is equivalent to finding the two fractions with a denominator smaller than n closest to a b (greater and lower). We look for two fractions f = p q and g = p q such that q ≤ n, q ≤ n, f ≤ a b ≤ g, and there is no fraction of denominator smaller or equal to n neither between f and a b nor between a b and g. This problem is closely related to the computation of the best rational approximation of a number, for which solutions using the decomposition into continuous fractions exist [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]. However, we do not need only the best approximation, which is either the closest lower or closest greater fraction, but also the other one. To solve this problem, we use the algorithm of Charrier and Buzer [START_REF] Charrier | Approximating a real number by a rational number with a limited denominator: A geometric approach[END_REF]. This algorithm aims at computing the approximation of any real number by rational numbers of bounded denominator and straightforwardly solves our problem in O(log(n)). Moreover the algorithm is simple to implement and does not require continuous fractions computations.

Locate a lower edge

At this point, we work in a ladder defined by two fractions f = p q and g = p q of F n . This step consists in localising Λ in the ladder by computing the highest ray under Λ in F n . In [START_REF] Mcilroy | A Note on Discrete Representation of Lines[END_REF], this step is performed as a binary search among the rays of the ladder. However, each stage of the binary search requires to solve a diophantine equation with the extended Euclidean algorithm, reaching a total complexity of O(log 2 n). Our algorithm, presented in Algorithm 1 and illustrated in Figure 3, also performs a dichotomy (line 4), but only on the rays of smallest slope passing through the points of abscissa p q (in red in Figure 3). Thanks to Property 4, this set of points can be defined as on line 1, and the rays of smallest slope are computed in time O(1) in the ladder using Corollary 2 (line 2). On line 4, the ray of greatest slope is computed from the ray of smallest slope thanks to Property 3. On line 5, the value x is not an integer value, but the closest lower ray can be easily computed using Property 3.

Algorithm 1: Search in the ladder

Let v i = ( p q , i q ), i ∈ Z, 0 ≤ i ≤ q 1 Let R i (x i , y i ) be the ray of smallest slope passing through v i 2

Perform a dichotomy on the R i to compute j ∈ [|0, q -1|] such that Λ is In Figure 3, on the left, the point Λ is located under the ray of greatest slope passing through v j+1 (in green, line 4 in Algorithm 1), R j is returned. On the right, the point Λ is in between the rays passing through v j+1 : the slope of the line passing through v j+1 and Λ is computed (in blue, line 5 in Algorithm 1), and is rounded to find the nearest lower ray.

Experimentation

We have implemented the presented algorithm using the open-source library DGtal [1]1 . The algorithm is very easy to implement and does not require continuous fractions implementation as in [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Said | Computing the characteristics of a subsegment of a digital straight line in logarithmic time[END_REF]. The algorithms of Said and Lachaud [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Said | Computing the characteristics of a subsegment of a digital straight line in logarithmic time[END_REF] being implemented in this library, comparing the algorithms was then an easy task. We also conducted the experimentation along the same protocol as the one they proposed as a test file in DGtal. Basically, the idea is to randomly choose a maximal value N for the parameter b of the DSL (a is smaller than b), then fix a maximal value for the length n of the DSS, and finally randomly choose a shift µ and the abscissa of the DSS first point. Each experiment is conducted for 10000 randomly chosen parameters.

The algorithms are executed to compute the characteristics of the DSS contained in the DSL. For each algorithm, the total running time is measured and divided by the total number of trials. The first observation is that SmartDSS is clearly slower than the other two algorithms. The second observation concerns the behaviour of the curves: the execution time increases with n for our algorithm while it decreases for Re-versedSmartDSS. This is consistent with the complexities of the algorithms. The complexity of our algorithm is logarithmic in the length of the DSS while the complexity of ReversedSmartDSS depends on the difference of depth of the slope of the DSL and the slope of the DSS. Consequently, our algorithm is more efficient for short DSSs, while for ReversedSmartDSS, the greater is n, the smaller is the difference of slopes, and the more efficient is the algorithm.

It is thus interesting to study the value of n for which the two curves cross each other. We see in Figure 5 that this value is 10 4 for N = 10 6 and 10 6 for N = 10 9 . Other experiments show that this value is 10 3 for N = 10 4 and that the threshold ratio n N below which our algorithm is faster tends to decrease with N .

Conclusion

We have proposed an algorithm to compute the characteristics of a DSS which is a subsegment of a DSL of known characteristics. We use the Farey fan and its numerous arithmetical properties to design a very efficient both theoretically and practically, and easy to implement algorithm to solve this problem.

We prensented the algorithm in the case where the DSL parameters are rational fractions. However, it can be straightforwardly extended to deal with irrational parameters.

Figure 1 :

 1 Figure 1: (a) DSS of minimal characteristics (1, 3, 1) with its leaning points U, U , L, L . (c) Representation of P(S) is the (α, β) space.(b) Each vertex of the preimage maps to a straight line in the digital space. The vertex B(13 , 1 3 ) maps to the upper leaning line, the characteristics of which are the minimal characteristics of the DSS.

Figure 2 :

 2 Figure 2: (a) Farey Fan of order 6. (b) Illustration of Properties 1 to 4 from Section 3.

Property 5 .

 5 A point v( pv qv , rv qv ) is the characteristic point of a facet if and only if:

Figure 3 :

 3 Figure 3: Illustration of Algorithm 1: the dichotomy is performed on the red rays only.

3 above 4 else 6 Return

 346 R j and below R j+1 if Λ is under the ray of greatest slope through v j+1 then Return R j Compute the slope x of the line passing through v j+1 and Λ 5 Compute [x] as the value x j+1 + kq nearest to and lower than x, k ∈ Z R([x], (j+1)+p.[x] q ) 7

Figure 5

 5 represents the results obtained for N = 10 6 in (a) , N = 10 9 in (b) and n taking all the value of the form 10.2 k in the interval [10, N ]. The graph represents the execution time in ms versus the maximal length n of the DSS.

The C++ code of this algorithm is freely available on the webpage http://www. gipsa-lab.grenoble-inp.fr/ ~isabelle.sivignon.

Find the characteristic point

Let us denote by M and N the two points defined as the intersection between the ray R(x, y) returned by Algorithm 1 and the vertical lines defining the ladder, i.e. α = p q and α = p q as defined in Section 4.1. The segment [M N ] is part of a lower edge of the facet of F n containing Λ in F n .

The first step of the algorithm detailed in Algorithm 2 is to compute the extremities of the lower edge containing [M N ]. To do so, the key point is to use Property 1 to characterize the points of intersection between a ray and other rays. Given a ray R(x, y) of the Farey Fan F n and a point v( p q , r q ) on this ray, v is the crossing point of several rays if and only if q ≤ max(x, nx). Thus, the abscissa of the (resp. right) extremity of the lower edge is given by the term of the Farey series of order max(x, nx) lower than (resp. greater than) and closest to p q (resp. p q ) (line 1 of Algorithm 2). Given a fraction, computing the next term in a Farey series of given order cannot be solved in constant time but requires a call to the extended Euclidean algorithm. From these two fractions p q and p q we compute the two points O of R with abscissa equal to p q and O of R with abscissa equal to p q (line 2). At this point, [OO] is a lower edge of the facet containing Λ. Then, the three cases illustrated in Figure 4 can occur: either O or O is the characteristic point (case (a) and (b)), or not (case (c)). We use Property 5 to distinguish between these cases:

the condition line 3 refers to Corollary 1;

• if R is the ray of greatest slope in O, then O is the characteristic point: the condition line 4 refers to Corollary 1;

• otherwise, the facet is lower triangular, and the abscissa of the characteristic point is given by the mediant of the abscissae of the lower edge extremities, i.e. O and O (direct consequence of Property 1): on line 5, the mediant is computed, and the point of R with this abscissa is the characteristic point.

Complexity

Lemma 1. The complexity of the algorithm described in Section 4 is in

where n is the length of the DSS.

Proof. We assume a computing model where standard arithmetic operations are done in constant time. Finding the ladder is done using the algorithm of Charrier and Buzer [START_REF] Charrier | Approximating a real number by a rational number with a limited denominator: A geometric approach[END_REF] that has a complexity of O(log(n)).

The localization of a lower edge is done with Algorithm 1: the computation of the R i (line 2) is done in constant time thanks to Corollary 2, such that the global complexity of lines 2 and 3 is O(log(q)) with q ≤ n. The operations done Algorithm 2: Find the characteristic point Let R(x, y) be the ray output by Algorithm 1 Let M ( p q , r q ) and N ( p q , r q ) belonging to R Let p q and p q be the fractions before p q and after p q in the Farey Series of 1 order max(x, nx).

Let O (resp. O) be the intersection point between α = p q (resp. p q ) and R

Let p q = p+p q+q . Return the intersection point between α = p q and R 5 in lines 4 to 7 are done in constant time, and the complexity of Algorithm 1 is in O(log(q)).

Algorithm 2 performs the last step of the algorithm. On line 1, two calls to the extended Euclidean algorithm are necessary to compute the lower edge extremities, which takes O(log(n)). All the other operations of this algorithm take O(1), which ends the proof.

Algorithm 2 can actually be optimized so that the call to the extended Euclidean algorithm (line 1) is not always necessary. These optimizations consist in the study of particular cases that are not presented here to keep the algorithm as clear as possible. All in all they do not change the theoretical complexity but lower the constant term, and slightly improve the practical efficiency.

This algorithm solves Problem 2 in O(log(n)) where n is the order of the Farey fan. From the equivalence of Problems 1 and 2, this algorithm also solves Problem 1 in logarithmic time where n is the length of the DSS. [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Said | Computing the characteristics of a subsegment of a digital straight line in logarithmic time[END_REF] The exprimental section has shown that our algorithm is faster than the ReversedSmartDSS algorithm when the length of the DSS is sufficiently smaller than the DSL period. This suggests that the ReversedSmartDSS algorithm should be prefered when the DSL parameters are issued from the recognition of a DSS on an image, and that our algorithm would perform better to draw a DSS given by floating-point vertices on an image. It would however be interesting to deepen this comparison.