Thierry Chanier

Michael Pengelly

Knowledge Acquisition for Learner Modelling in Second Language Learning

Keywords: Learner modelling, Intelligent Tutoring System, Second Language Learning, Knowledge Acquisition

The results of past studies in Error Analysis in applied linguistics and the experiences of developers of intelligent tutoring systems in learner modelling have influenced our definition of a new structure, called an "applicable rule", that can be used to help diagnose and to represent a learner's performance in second language learning systems. Based on this structure a prototype interface has been designed to acquire the knowledge that it must contain. The results of experiments with this interface, to validate and to fill it, have been instrumental in refining its structure, pointing out the difficulties of transforming it into an automated acquisition device, and in indicating its potential as a teaching device.

Introduction

Computer-based learning environments that adapt sensitively to a learner require current methods of learner modelling to be improved. Generally speaking, earlier approaches to learner modelling in intelligent tutoring systems (ITSs) took account only of the immediately observable performance giving little or no consideration to the deeper underlying causes of the production of this behaviour. Without an understanding of these underlying misconceptions a more responsive adaptation of the environment to the learner is severely limited.

In pursuing a deeper modelling approach in second language learning we have followed the current approach of the applied linguistic community in viewing second language learning (SLL) as one of building and updating rules for language production through the use of heuristics and various strategies brought about by the circumstances in which learners find themselves, e.g. a pressing need to communicate. The process of learner modelling is to identify, not only this set of rules, but also their causal mechanisms, the learner's heuristics and strategies, that are currently active.

In order to represent these aspects of learner modelling we introduce the idea of an applicable rule (AR). This term stems from the concept of rules being modified to fit a particular situation and thus being seen as applicable to this situation. The applicable rule approach de-emphasises the idea of absolute correctness. This is desirable for several reasons: firstly, because we wish to encourage a learner's internal generation of applicable rules as a valuable part of learning, even if this leads at times to incorrect rules; secondly, because teachers themselves may wish to use applicable rules, as pedagogic devices to encourage learning, accepting the approximation to the desired language competence; and thirdly, the domain of language learning is less clear cut than those traditionally used for ITSs, such as mathematics or programming languages; hence correctness can depend on how the language is being used, for instance in speech or writing. This paper outlines the development of an interface that is a support tool for acquiring from language teachers their knowledge about why a learner produces a foreign language in certain ways. The design of this interface is based on an applicable rule framework that encapsulates the information necessary to diagnose how and why a learner has produced a particular sentence that diverges from that expected. The information collected from experiments with this interface, which is an early development stage in an evolving system, we call BELLOC, has led to the refinement of the structure of an applicable rule and to the design of an architecture (detailed in [START_REF] Chanier | A Prototype for the Acquisition of Rule-Based Student Models[END_REF]) to support the computer diagnosis of a learner's grammatical performance. As a by-product of this exercise we are able to suggest ways in which the interface could be used in an instructional role.

2.

An applicable rule, a structure for learner modelling

Many past ITSs have modelled the learner by a set of production rules which describe at some level of detail the possible "bugs" that a learner may have, where a bug is the discrepancy between the system's representation of a learner's behaviour in some problem solving situation and the system's conception of what that behaviour should be. Typically the anticipated discrepancies are held in a bug catalogue which has been prepared by observation and the meticulous analysis of learner's past performances. The development of these bug catalogues (which can run into several hundred rules) is labour intensive and is a task that can stretch over several years [START_REF] Anderson | Psychology and Intelligent Tutoring[END_REF]; it thus presents severe problems in modelling learners. Additionally, bug catalogues are concerned with relatively superficial differences in behaviour and not with the underlying misconceptions that gave rise to the bugs. It is the identification of these misconceptions that could guide more sensitively further interactions with the learner.

In second language learning this problem has been extensively investigated. The emphasis on deeper explanation of learners' performance has come from Error Analysis in applied linguistics where, starting with studies in the early 1970s [START_REF] Richards | Error Analysis: Perspectives on Second Language Acquisition[END_REF], second language learners were seen as actively constructing rules from the data they encountered, gradually adapting them in the direction of the target language system. This meant that the learners' errors needed no longer to be seen as signs of failure. On the contrary, they gave some evidence for the learners developing their systems of rules. Arising from these studies different cognitive processes were proposed that gave possible explanations of errors [START_REF] Ellis | Understanding second language acquisition[END_REF]. The commonly known one is that of language transfer where the learner uses his mothertongue (or sometimes knowledge of another foreign language) to organise constructs in the new foreign language. Another explanation for irregular sentence construction is the emphasis that is placed on some aspect by the teacher or text book that causes the learner to over-use a construct. More interesting from the point of view of learner modelling are the strategies of learning and communication that are used to build new rules. Some strategies that the user may employ to simplify the task of learning are: over-generalisation where the learner applies a rule too widely; not knowing about restrictions on the use of rules; or incomplete application of a rule. Communication strategies are also important as a source of ungrammatical but understandable sentences. These are employed because the learner lacks the linguistic resources to express his intended meaning.

Although this deeper analysis of learners' behaviour is particularly beneficial in determining remediation strategies, since it identifies gaps in the acquisition process itself as well as the acquired knowledge, its disadvantage is that it is time consuming and suitable only for one-to-one tutoring. Thus it is an obvious candidate for computer-based teaching.

For an ITS there will be consequences for the process of building rules that account for stronger links between the learner's behaviour and its explanation 1 . This lead us to the concept of a structured applicable rule (Fig. 1). A central feature of the structure are the elements that represent the different explanations that can be given for the divergence of the grammar of the learner's sentence from some standard grammar. We talk about "divergent sentences" because the appreciation of the level of correctness will vary, depending on such conditions as: the state of the learner, the language objectives, and the context within which the sentence was produced. The explanations are expected to be of two forms grammatical and causal. The grammatical explanations describe in some meta-language, that the teacher thinks is appropriate to the particular type of learner, what the error is. The causal explanations will be along the lines of the basic misconceptions introduced in Error Analysis. Each separate description of a grammatical divergence will give rise to a separate applicable rule, but different descriptions of the same divergence will count as a single rule. The occurrence of multiple explanations also requires that the applicable rules can be related to one another and possibly to the computational grammar form of the rule or its standard counterpart.

Since there are likely to be several explanations of the same divergence some means of discriminating between them will be necessary. Teachers commonly use a dialogue containing examples and counter-examples as a method of differentiating between competing explanations of a learner's performance, hence this information must be gathered. How an applicable rule relates to a particular divergent sentence, and how it can be automatically selected as a possible candidate to explain the divergence is described by its computational code. Since applicable rules can be of very different sorts, procedures can be expressed in a computational linguistic formalism, or in a pedagogical grammar formalism or as meta-rules.

Interface for the Acquisition of Applicable Rules (IFAAR)

In order to acquire the information needed to fill the slots of the applicable rule structure, described above, we needed to develop knowledge acquisition techniques. The method that we chose was that of providing a structured interface and stimulating a dialogue with the user by means of concrete examples. That is we presented a sentence, that a learner had produced, to a user, normally an experienced teacher, and asked him or her to comment on it by entering text into various windows of a computer interface that corresponded to elements of the applicable rule.

The principal features of the interface, called IFAAR, are illustrated in Fig. 2. The windows provide a loosely structured environment that reflects the uncertainty that there inevitably is in the first iteration of knowledge acquisition. By keeping the interface as flexible as possible we have attempted to encourage the users to provide their own interpretations of the kinds of information that they believe they use in diagnosing a learner's divergent performance but this has been at the cost of providing any automatic support.

Figure 2 General view of IFAAR window system

We have provided a focus for the expert by offering a selection of typical learners' divergent sentences for analysis. The sentences came from a problem solving exercise with a simulated system which encouraged English learners to produce interrogative sentences in French about family relationships. The windows labelled Divergent Sentence, Sentence Context, Parser Diagnosis, and Computational Error Rule provide the principal information that the analyst requires to make entries into the other windows, those that correspond to elements of the applicable rule framework. Supplementary information can be accessed by means of a "button menu" in the window labelled Linguistic Knowledge. This provides access to the parser with which examples may be checked. Windows associated with the applicable rule structure are opened via the Applicable Rule window. Data can be entered into these windows in any order. Multiple Explanation windows can be created for any one applicable rule. Relation entries were restricted in this version to hierarchical entries via the Parent Node box in the Applicable Rule window. The widow marked Computational Code would not be filled in by the teacher but by a computational linguist or the system designer, depending on the type of applicable rule created (see section 4). All window creation is by means of the mouse and buttons. All windows are scrollable and may be resized, moved and quit. A more detailed description of the use of this environment is given in [START_REF] Chanier | A Prototype for the Acquisition of Rule-Based Student Models[END_REF].

4.

Experiments with IFAAR

Our experiments with IFAAR had two aims. The main one was to accumulate information about how experienced teachers diagnosed learner's performances during the learning of a foreign language. A subsidiary aim, which we will not develop here, was to refine the interface as a step towards making it an autonomous knowledge acquisition tool.

Although the system was designed for use by expert teachers we wanted to find out if advanced learners or new teachers could offer insights into how language is acquired that was radically different from the teachers' views. The interface provided an unsatisfactory means of doing this. Neither of the learners had sufficient knowledge of formal aspects of a language to be able to formulate descriptions of the observed behaviour nor were they able to articulate why they or others would produce the sentences. The value of having them use the system was that it introduced us to a potential method of aiding language acquisition; that of having a learner reflect on others' and their own mistakes within a structured environment. We also found that one of the novice teachers, whose approach to teaching language was communicative and whose major experience was with absolute beginners, was not capable of providing us with useful entries.

Different kinds of explanations

The explanations offered by the teachers of the learners' performances fell into three types corresponding to: why the performances occurred (causal explanation), what the performance was; and what performance would have been desirable. The last two types of explanation are grammatical ones, one corresponding to the learner's point of view as expressed by the user, the other one to the user's point of view on what is "correct". In order to avoid the confusion of defining at the same time and in the same place these two aspects, we think it is better to distinguish between learner applicable rules , which would characterise the learner's performance, and teacher applicable rules which would define what it should have been. The user could then define a relationship between a learner and a teacher AR. In fact, the set of teacher applicable rules correspond to a pedagogical grammar. The idea of having teacher ARs as well as learner ones also reflects a degree of equivalence between both agents, since the teacher may also be applying a subset of these rules to approximate the desired language competence as a pedagogic device to simplify the learning process.

There is evidence for there being two levels of causal explanation. One level of explanation suggests why the learner does not have the required rule, through forgetting or ignorance. In this case the diagnosis can be extracted from the learner's history. Causal explanations relating to this aspect were restricted by the limited data available in IFAAR. The other level of causal explanation suggests why the learner has acquired or generated the current applicable rule that produced the divergent performance. Explanations collected in the experimental data were those commonly presented in texts on SLL of language transfer, over-generalisation, simplification, etc. Hence it may emerge that a hierarchy of explanations can be constructed which may determine the method of remediation or future pedagogical strategies.

Meta-Language and pedagogical grammar

Grammatical explanations, were given at different levels of formality, the level of formality being dependent on the perceived audience. Hence the meta-language used to describe the rule was sometimes in the technical vocabulary of the linguist, at other times in a semi-formal language suitable for those with a developed knowledge of grammar, and sometimes in informal terms for those with little or no knowledge of grammar. At one extreme of this spectrum of descriptions could be placed the computational form of the applicable rule that, we are now aware, must be generated by a computational linguist, and at the other extreme is an implied description of the performance provided by offering the learners sets of examples and counter-examples and allowing them to induce their own form of the rules.

We believe a consistent meta-language is necessary to provide grammatical explanations. This grammar in the BELLOC system represents the teacher's point of view on the linguistic knowledge which is to be learned. It cannot be the computational grammar (see the discussion in [START_REF] Chanier | Conceptual Modelling in Error Analysis in Computer-Assisted Language Learning Systems[END_REF]), but it will need to be a formally defined pedagogic grammar, since, besides its description and implementation being indispensable for teaching purposes, it must function computationally to help in the diagnosis of the learner's divergences.

Roles played by the examples

Although the examples and reject examples collected could not in themselves provide guidance in any classification scheme, the verbal comments of the users suggest that they are used in at least three ways: to disambiguate competing explanations of a divergent performance, to refine an explanation, and as teaching devices (forcing the learners to build their applicable rules by induction).

Whatever role they play, it was emphasised by our expert teachers that examples play an important role in the pedagogical process. The reject examples can mainly be used as discriminatory examples between competing ARs. The positive examples can facilitate the learner's understanding of the grammatical explanations extracted from the ARs that BELLOC will use. Since examples must be linguistically and pedagogically relevant they need to be generated by hand by experts through IFAAR.

What kinds of applicable rules for IFAAR ?

From the experiments made with IFAAR and parallel investigations on ways to automate the generation of applicable rules, we have distinguished at least three kinds of applicable rules (more fully described in [START_REF] Chanier | Conceptual Modelling in Error Analysis in Computer-Assisted Language Learning Systems[END_REF]):

-pedagogical grammar rules: these correspond to the pedagogical grammar. They should be created by the designers of BELLOC. -meta-rules: some of them will operate on the pedagogical grammar rules in order to simulate, for example, the learner's processes of simplification and then generate automatically a learner's applicable rule. They should also be created by the designers. -predefined rules: they describe specific linguistic difficulties that only an expert teacher can predict. These rules are those which should be acquired through IFAAR.

IFAAR as a teaching device

IFAAR could be used in its present state (or with minor changes and adaptations) as a teaching device, relevant either for the teacher or the learner. For a given learner, the exercise of generating applicable rules from divergent sentences uttered by another learner can be a good way of imposing self reflection on his own system of rules. The reflection may come from the verbalisation of the rules, the examples produced, and from the different possible viewpoints on the given problem that will be achieved through generating, at the same time, one or several applicable rules accounting for what he guesses the other learner has done, and another applicable rule on what he thinks the remediation could be. In achieving this task, the learner will handle the language from different aspects: from a given sentence, he will give a translation, a remediation, examples and counter-examples, take the context into consideration, etc. IFAAR may also be relevant for the teacher. The teacher's analysis of the results of the work done by his students in an IFAAR session can be useful to identify their grammatical competence. The evaluation of grammatical competence is an important matter in order to meet the learner's needs [START_REF] Tarone | Focus on the Language Learner: Approaches to identifying and meeting the needs of second language learners[END_REF]. But it is considered as being difficult to achieve through making judgements and corrections only on examples. It also requires tests to be undertaken in different situations: written, narrative, communicative,.etc. We hope that with IFAAR we will have almost all these requirements. This analysis may also give the teacher feedback on his teaching: when looking at the learners' rules, he may induce some relations with his own presentation of the rules. The expert teachers who have used the system told us that they found their situation interesting and quite unusual. In fact, a large part of what has been said about the learner could apply to the teacher as well. For an experienced teacher, or even more a trainee teacher, the use of IFAAR may bring useful reflection about how to teach rules, illustrate different perspectives, study the connection between their pedagogical grammar and the descriptive/computational grammar.

Conclusions

We have focussed on acquiring knowledge about the source of learners' language production rules as accounted for by expert teachers. We have proposed the uniform structure of an applicable rule into which this knowledge might fit. The window-based interface IFAAR, reflecting this structure, has been implemented and used in experiments with expert and novice teachers. From these experiments we have begun to validate the structure of an applicable rule and we also get a better view on how to automatically support the expert in the knowledge acquisition process. This may be useful for ITS in all domains [START_REF] Twidale | Knowledge Acquisition for Intelligent Tutoring Systems[END_REF]. In the future, this acquisition will mainly focus on a certain kind of applicable rules, we called "predefined," which encompass an expertise on the learner both indispensable in a computerassisted language learning system and hardly automatically obtainable from any calculation. Finally, we pointed out how such environments for knowledge acquisition from experts could profitably be used as a means of teaching for learners or for trainee teachers.

Figure 1 :

 1 Figure 1: Structure of an applicable rule

Different perspectives adopted by other ITSs on SLL and their limitations are presented in[START_REF] Chanier | Conceptual Modelling in Error Analysis in Computer-Assisted Language Learning Systems[END_REF].

Acknowledgements

This research was partially funded by the CEC NAT*LAB project within the exploratory action of the DELTA programme and by the Institut National de Recherche en Informatique et Automatique (INRIA, France). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies of DELTA or INRIA. The authors would like to acknowledge the contributions of Michael Twidale, for his participation in the specifications and the development of the IFAAR prototype, and John Self for his constructive criticisms.


Nicolas Bonichon
email: bonichon@labri.fr

Cyril Gavoille
email: gavoille@labri.fr

Nicolas Hanusse
email: hanusse@labri.fr

Ljubomir Perković
email: lperkovic@cs.depaul.edu

The Stretch Factor of L 1 -and L ∞ -Delaunay Triangulations

Keywords: Delaunay triangulations, L 1 -metric, L ∞ -metric, stretch factor

In this paper we determine the stretch factor of the L 1 -Delaunay and L ∞ -Delaunay triangulations, and we show that this stretch is 4 + 2 √ 2 ≈ 2.61. Between any two points x, y of such triangulations, we construct a path whose length is no more than 4 + 2 √ 2 times the Euclidean distance between x and y, and this bound is best possible. This definitively improves the 25-year old bound of √ 10 by Chew (SoCG '86). To the best of our knowledge, this is the first time the stretch factor of the well-studied L p -Delaunay triangulations, for any real p ≥ 1, is determined exactly.

Introduction

Given a set of points P on the plane, the Delaunay triangulation for P is a spanning subgraph of the Euclidean graph on P that is the dual of the Voronoï diagram of P . The Delaunay triangulation is a fundamental structure with many applications in computational geometry and other areas of Computer Science. In some applications (including on-line routing [START_REF] Bose | Competitive online routing in geometric graphs[END_REF]), the triangulation is used as a spanner, defined as a spanning subgraph in which the distance between any pair of points is no more than a constant multiplicative ratio of the Euclidean distance between the points. The constant ratio is typically referred to as the stretch factor of the spanner. While Delaunay triangulations have been studied extensively, obtaining a tight bound on its stretch factor has been elusive even after decades of attempts.

In the mid-1980s, it was not known whether Delaunay triangulations were spanners at all. In order to gain an understanding of the spanning properties of Delaunay triangulations, Chew considered related, "easier" structures. In his seminal 1986 paper [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF], he proved that an L 1 -Delaunay triangulation -the dual of the Voronoï diagram of P based on the L 1 -metric rather than the L 2 -metric -has a stretch factor bounded by √ 10. Chew and showed that the a TD-Delaunay triangulation -the dual of a Voronoï diagram defined using a Triangular Distance, a distance function not based on a circle (L 2 -metric) or a square (L 1 -metric) but an equilateral triangle -has a stretch factor of 2 [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF].

Finally, Dobkin et al. [START_REF] Dobkin | Delaunay graphs are almost as good as complete graphs[END_REF] succeeded in showing that the (classical, L 2 -metric) Delaunay triangulation of P is a spanner as well. The bound on the stretch factor they obtained was subsequently improved by Keil and Gutwin [START_REF] Keil | Classes of graphs which approximate the complete Euclidean graph[END_REF] as shown in Table 1. The bound by Keil and Gutwin stood unchallenged for many years until very recently when Xia improved the bound to below 2 [START_REF] Xia | Improved upper bound on the stretch factor of delaunay triangulations[END_REF].

While progress has been made, none of the techniques developed so far lead to a tight bound on the spanning ratio. There has been some progress recently on the lower bound side. The trivial lower bound of π/2 ≈ 1.5707 has recently been improved to 1.5846 [BDL + 11] and then to 1.5932 [START_REF] Xia | Toward the tight bound of the stretch factor of Delaunay triangulations[END_REF].

While much effort has been made on understanding the stretch factor of Delaunay triangulations, little has been done on the L p -Delaunay triangulations for p = 2. Lee and Wong [START_REF] Lee | Voronoï diagrams in L 1 (L ∞ ) metrics with 2dimensional storage applications[END_REF] show that L 1 -,L ∞ -Delaunay triangulations have applications in scheduling problems for 2-dimensional storage, and how to construct, for all real p ≥ 1, Voronoï diagrams in the L p -metric in O(n log n) time [START_REF] Lee | Two-dimensional Voronoi diagrams in the L p -metric[END_REF]. Delaunay triangulations based on arbitrary convex distance functions have been studied in [START_REF] Bose | On the stretch factor of convex Delaunay graphs[END_REF], which shows that such geometric graphs are indeed plane graphs and spanners whose stretch factor depends only on the shape of the convex body. However, due to the general approach, the bounds on the stretch factor remain loose. For instance the bounds they obtain for L 2 -Delaunay triangulations are > 24.

The general picture is that, in spite of much effort, with the exception of the triangular distance the exact value of the stretch factor of Delaunay triangulations based on any convex function is unknown. In particular, the stretch factor of L p -Delaunay triangulations is unknown for each p ≥ 1.

Our contributions. We show that the exact stretch factor of L 1 -Delaunay triangulations and L ∞ -Delaunay triangulations is 4 + 2 √ 2 ≈ 2.61, ultimately improving the 3.16 bound of Chew [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF].

Technically, we use rectangular coordinates to prove the upper bound. We show that the distance in the triangulation between any source-destination pair of points lying on the border of a horizontal rectangle of length x and of depth y ≤ x is no more than (1 + √ 2)x + y. The stretch factor bound then simply follows. In our proof, we construct the route from the source to the destination by maintaining two possible short paths, until we reach some special point (called inductive point) where we can apply our main inductive hypothesis.

Despite the technical aspect of our contribution, we believe that our proof techniques may give insights into determining the stretch factor of other convex distance based Delaunay triangulations. For example, let P k denote the convex distance function defined by a regular k-gon. We observe that the stretch factor of P k -Delaunay triangulations is known for k = 3, 4 since P 3 is the triangular distance function of [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF], and P 4 is nothing else than the L ∞ -metric. Determining the stretch factor of P k -Delaunay triangulations for larger k would undoubtedly be an important step towards understanding the stretch factor of classical Delaunay triangulations.

Preliminaries

Given a set P of points in the two-dimensional Euclidean space, the Euclidean graph E is the complete weighted graph embedded in the plane whose nodes are identified with the points. We assume a Cartesian coordinate system is associated with the Euclidean space and thus every point can be specified with x and y coordinates. For every pair of nodes u and w, the edge (u, w) represents the segment [uw] and its weight is the edge length defined in Euclidean distance: d 2 (u, w) = d x (u, w) 2 + d y (u, w) 2 where d x (u, w) (resp. d y (u, w)) is the difference between the x (resp. y) coordinates of u and w.

We say that a subgraph H of a graph G is a t-spanner of G if for any pair of vertices u, v of G, the distance between u and v in H is at most t times the distance between u and v in G; the constant t is referred to as the stretch factor of H (with respect to G). H is a t-spanner (or spanner for some t constant) if it is a t-spanner of E.

In our paper, we deal with the construction of spanners based on Delaunay triangulations. As we saw in the introduction, the L 1 -Delaunay triangulation is the dual of the Voronoï diagram based on the L 1 -metric d 1 (u, w) = d x (u, w) + d y (u, w). A property of the L 1 -Delaunay triangulations, actually shared by all L p -Delaunay triangulations, is that all their triangles can be defined in terms of empty circumscribed convex bodies (squares for L 1 or L ∞ and circles for L 2 ). More precisely, let a square in the plane be a square whose sides are parallel to the x and y axis and let a tipped square be a square tipped at 45 • . For every pair of points u, v ∈ P , (u, v) is an edge in the L 1 -Delaunay triangulation of P iff there is a tipped square that has u and v on its boundary and contains no point of P in its interior (cf. [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF]).

If a square with sides parallel to the x and y axes, rather than a tipped square, is used in this definition then a different triangulation is defined; it corresponds to the dual of the Voronoï diagram based on the L ∞ -metric d ∞ (u, w) = max{d x (u, w), d y (u, w)}. We refer to this triangulation as the L ∞ -Delaunay triangulation. This triangulation is nothing more than the L 1 -Delaunay triangulation of the set of points P after rotating all the points by 45 • around the origin. Therefore Chew's bound of √ 10 on the stretch factor of the L 1 -Delaunay triangulation ( [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF]) applies to L ∞ -Delaunay triangulations as well. In the remainder of this paper, we will be referring to L ∞ -Delaunay (rather than L 1 ) triangulations because we will be (mostly) using the L ∞ -metric and squares, rather than tipped squares.

One issue with Delaunay triangulations is that there might not be a unique triangulation of a given set of points P . To insure uniqueness and keep our arguments simple, we make the usual assumption that the points in P are in general position, which for us means that no four points lie on the boundary of a square and no two points share the same abscissa or the same ordinate.

We end this section by giving a lower bound on the stretch factor of L ∞ -Delaunay triangulations.

Proposition 1 For every ε > 0, there exists a set of points P in the plane such that the L ∞ -Delaunay triangulation on P has stretch factor at least

4 + 2 √ 2 -ε .
This lower bound applies, of course, to L 1 -Delaunay triangulations as well. The proof of this proposition relies on the example of Figure 1.

Proof. Given δ > 0, we define the set of points P as follows. Let point a be the origin and let points b, c 1 , and δ and thus k is an integer so that this can be done.) Let a = p 0 , p 1 , p 2 , p 3 , . . . , p k , p k+1 = c 1 be the labels, in order as they appear when moving from a to c 1 , of the points on segment [ac 1 ] and let c 2 = q 0 , q 1 , q 2 , q 3 , . . . , q k+1 = b be the labels, in order as they appear when moving from c 2 to b, of the points on segment [c 2 b], as illustrated in Figure 1.

c 2 have coordinates (1, √ 2 -1), (δ, √ 2 -2δ), and (1 -δ, 1 -2δ), respectively. Additional k = √ 2-2δ δ -1
Consider the square S 1 of side length 1 -δ and having a and p 1 on its west (left) and north sides, respectively (see Figure 1b)

). Since d ∞ (a, c 2 ) = d x (a, c 2 ) = 1-δ and d ∞ (p 1 , c 2 ) = d y (p 1 , c 2 ) = 1 -δ, point c 2 is exactly the southeast vertex of square S 1 . By symmetry, it a c 2 c 1 b 1 -2δ 1 -δ √ 2 -2δ √ 2 -1 1 -2δ S 1 c 2 q 1 a p 1 p 2 δ a) b)
Figure 1: a) An L ∞ -Delaunay triangulation with stretch factor arbitrarily close to 4 + 2 √ 2. b) A closer look at the first few faces of this triangulation.

follows that for every i = 0, 1, 2, . . . , k, if S i is the square of side length 1 -δ with p i and p i+1 on its west and north sides, then point q i is exactly the southeast vertex of S i . This means that all points q j with j = i as well as all points p j with j = i, i + 1 must lie outside S i . Therefore, for every i = 0, 1, 2, . . . , k, points p i , p i+1 , and q i define a triangle in the L ∞ -Delaunay triangulation T on P . A similar argument shows that the path q 0 , q 1 , . . . , q k+1 is in triangulation T as well. The triangulation T is illustrated in Figure 1a).

Having defined the set of points P and described its L ∞ -Delaunay triangulation T , we now analyze the stretch factor of T . A shortest path from a to b in T is, for example, a, p 1 , p 2 , . . . , p k , c 1 , b. The length of this path is

d 2 (a, c 1 ) + d 2 (c 1 , b) = d x (a, c 1 ) 2 + d y (a, c 1 ) 2 + d x (c 1 , b) 2 + d y (c 1 , b) 2 = ( √ 2 -δ) 2 + δ 2 + (1 -δ) 2 + (1 -2δ) 2
which tends to 2 √ 2 as δ tends to 0. The Euclidean distance between a and b is:

d 2 (a, b) = 1 2 + ( √ 2 -1) 2 = 4 -2 √ 2 .
Therefore, it is possible to construct a L ∞ -Delaunay triangulation whose stretch factor is arbirtrarily close to:

2 √ 2 4 -2 √ 2 = 4 + 2 √ 2 .

Main result

In this section we obtain a tight upper bound on the stretch factor of an L ∞ -Delaunay triangulation. It follows from this key theorem:

Theorem 2 Let T be the L ∞ -Delaunay triangulation on a set of points P in the plane and let a and b be any two points of over values x and y such that 0 < y ≤ x. The maximum is reached when x and y satisfy y/x = 1 + √ 2, and the maximum is equal to

P . If x = d ∞ (a, b) = max{d x (a, b), d y (a, b)} and y = min{d x (a, b), d y (a, b)} then d T (a, b) ≤ (1 + √ 2)x +
1 + (1 + √ 2) 2 = 4 + 2 √ 2.
As L 1and L ∞ -Delaunay triangulations have the same stretch factor, this result also holds for L 1 -Delaunay triangulations.

To prove Theorem 2, we will construct a bounded length path in T between two arbitrary points a and b of P . To simplify the notation and the discussion, we assume that point a has coordinates (0, 0) and point b has coordinates (x, y) with 0 < y ≤ x. The segment [ab] divides the Euclidean plane into two half-planes; a point in the same half-plane as point (0, 1) is said to be above segment [ab], otherwise it is below. Let T 1 , T 2 , T 3 , . . . , T k be the sequence of triangles of triangulation T that line segment [ab] intersects when moving from a to b. Let h 1 and l 1 be the nodes of T 1 other than a, with h 1 lying above segment [ab] and l 1 and lying below. Every triangle T i , for 1 < i < k, intersects line segment [ab] twice; let h i and l i be the endpoints of the edge of T i that intersects segment [ab] last, when moving on segment [ab] from a to b, with h i being above and l i being below segment [ab]. Note that either h i = h i-1 and T i = △(h i , l i , l i-1 ) or l i = l i-1 and T i = △(h i-1 , h i , l i ), for 1 < i < k. We also set h 0 = l 0 = a, h k = b, and l k = l k-1 . For 1 ≤ i ≤ k, we define S i to be the square whose sides pass through the three vertices of T i (see Figure 2); since T is an L ∞ -Delaunay triangulation, the interior of S i is devoid of points of P . We will refer to the sides of the square using the notation: N (north), E (east), S (south), and W (west). We will also use this notation to describe the position of an edge connecting two points lying on two sides a square: for example, a WN edge connects a point on the west and a point on the N side. We will say that an edge is gentle if the line segment corresponding to it in the graph embedding has a slope within [-1, 1]; otherwise we will say that it is steep.

We will prove Theorem 2 by induction on the distance, using the L ∞ -metric, between a and b. Let R(a, b) be the rectangle with sides parallel to the x and y axes and with vertices at points a and b. If there is a point of P inside R(a, b), we will easily apply induction. The case when R(a, b) does not contain points of P -and in particular the points h i and l i for 0 < i < k -is more difficult and we need to develop tools to handle it. The following Lemma describes the structure of the triangles T 1 , . . . , T k when R(a, b) is empty. We need some additional terminology first though: we say that a point u is above

(resp. below ) R(a, b) S 1 S 2 S 3 b a h 1 l 1,2 h 2,3 l 3 Figure 2:
Triangles T 1 (with points a, h 1 , l 1 ), T 2 (with points h 1 , h 2 , and l 2 ), and T 3 (with points l 2 , h 3 , and l 3 ) and associated squares S 1 , S 2 , and S 3 . When traveling from a to b along segment [a, b], the edge that is hit when leaving T i is (h i , l i ).

if 0 < x u < x and y u > y (resp. y u < 0).

Lemma 4 If (a, b) ∈ T and no point of P lies inside rectangle R(a, b), then point a lies on the W side of square S 1 , point b lies on the E side of square S k , points h 1 , . . . , h k all lie above R(a, b), and points l 1 , . . . , l k all lie below R(a, b). Furthermore, for any i such that 1 < i < k:

a) Either T i = △(h i-1 , h i , l i-1 = l i )
, points h i-1 , h i , and l i-1 = l i lie on the sides of S i in clockwise order, and andl i-1 lie on the sides of S i in clockwise order, and (l i-1 , l i ) is a WS, WE, or SE edge in S i .

(h i-1 , h i ) is a WN, WE, or NE edge in S i b) Or T i = △(h i-1 = h i , l i-1 , l i ), points h i-1 = h i , l i ,
These properties are illustrated in Figure 2.

Proof. Since points of P are in general position, points a, h 1 , and l 1 must lie on 3 different sides of S 1 . Because segment [ab] intersects the interior of S 1 and since a is the origin and b is in cone 0 of a, a can only lie on the W or S side of S 1 . If a lies on the S side then l 1 = b would have to lie inside R(a, b), which is a contradiction. Therefore a lies on the W side of S 1 and, similarly, b lies on the E side of S k .

Since points h i (0 < i < k) are above segment [ab] and points l i (0 < i < k) are below segment [ab], and because all squares S i (0 < i < k) intersect [ab], points h 1 , . . . , h k all lie above R(a, b), and points l 1 , . . . , l k all lie below R(a, b).

The three vertices of T i can be either h

i = h i-1 , l i-1
, and l i or h i-1 , h i , and l i-1 = l i . Because points of T are in general position, the three vertices of T i must appear on three different sides of S i . Finally, because h i-1 and h i are above R(a, b), they cannot lie on the S side of S i , and because l i-1 and l i are below R(a, b), they cannot lie on the N side of S i .

If T i = △(h i-1 , h i , l i-1 = l i ), points h i-1 , h i , l i must lie on the sides of S i in clockwise order. The only placements of points h i-1 and h i on the sides of S i that satisfy all these constraints are as described in a). If T i = △(h i-1 = h i , l i-1 , l i ), points h i , l i , l i-1 must lie on the sides of S i in clockwise order. Part b) lists the placements of points l i-1 and l i that satisfy the constraints.

In the following definition, we define the points on which induction can be applied in the proof of Theorem 2.

Definition 5 Let R(a, b) be empty. Square S j is inductive if edge (l j , h j ) is gentle. The point c = h j or c = l j with the larger abcissa is the inductive point of inductive square S j .

The following lemma will be the key ingredient of our inductive proof of Theorem 2.

Lemma 6 Assume that R(a, b) is empty. If no square S 1 , . . . , S k is inductive then d T (a, b) ≤ (1 + √ 2)x + y .
Otherwise let S j be the first inductive square in the sequence S 1 , S 2 , . . . , S k . If h j is the inductive point of S j then

d T (a, h j ) + (y h j -y) ≤ (1 + √ 2)x h j . If l j is the inductive point of S j then d T (a, l j ) -y l j ≤ (1 + √ 2)x l j .
Given an inductive point c, we can use use Lemma 6 to bound d T (a, b) and then apply induction to bound d T (b, c), but only if the position of point c relative to the position of point b is good, i.e., if x -x c ≥ |y -y c |. If that is not the case, we will use the following Lemma:

Lemma 7 Let R(a,

b) be empty and let the coordinates of point

c = h i or c = l i satisfy 0 < x -x c < |y -y c |.
a) If c = h i , and thus 0 < x -x h i < y h i -y, then there exists j, with i < j ≤ k such that all edges in path h i , h i+1 , h i+2 , . . . , h j are NE edges in their respective squares and x -x h j ≥ y h j -y ≥ 0.

b) If c = l i , and thus 0 < x -x l i < y -y l i , then there exists j, with i < j ≤ k such that all edges in path l i , l i+1 , l i+2 , . . . , l j are SE edges and x -x l j ≥ y -y l j ≥ 0.

Proof. We only prove the case c = h j as the case c = l i follows using a symmetric argument.

We construct the path h i , h i+1 , h i+2 , . . . , h j iteratively. If h i = h i+1 , we just continue building the path from h i+1 . Otherwise, (h i , h i+1 ) is an edge of T i+1 which, by Lemma 4, must be a WN, WE, or NE edge in square S i+1 . Since the S side of square S i+1 is below R(a, b) and because x -x h i < y h i -y, point h i cannot be on the W side of S i+1 (otherwise b would be inside square S i+1 ). Thus (h i , h i+1 ) is a NE edge. If x -x h i+1 ≥ y h i+1 -y we stop, otherwise we continue the path construction from h i+1 .

We can now prove the main theorem.

Proof of Theorem 2. The proof is by induction on the distance, using the L ∞ -metric, between points of P (since P is finite there is only a finite number of distances to consider).

Let a and b be the two points of P that are the closest points, using the L ∞ -metric. We assume w.l.o.g. that a has coordinates (0, 0) and b has coordinates (x, y) with 0 < y ≤ x. Since a and b are the closest points using the L ∞ -metric, the largest square having a as a southwest vertex and containing no points of P in its interior, which we call S a must have b on its E side. Therefore (a, b) is an edge in T and

d T (a, b) = d 2 (a, b) ≤ x + y ≤ (1 + √ 2)x + y.
For the induction step, we again assume, w.l.o.g., that a has coordinates (0, 0) and b has coordinates (x, y) with 0 < y ≤ x. We now assume that there is no point inside region B. If there is still a point in R(a, b) then there must be one that is on the border of S a , the square we defined in the basis step, or S b , defined as the largest square having b as a northeast vertex and containing no points of P in its interior. W.l.o.g., we assume the former and thus there is an edge (a, c) ∈ T such that either y c > x c (i.e., c is inside region A shown in Figure 3 or y -

y c > x -x c (i.e., c is inside region C). Either way, d T (a, c) = d 2 (a, c) ≤ x c + y c . If c is in region A, since x -x c ≥ y -y c , by induction we also have that d T (c, b) ≤ (1 + √ 2)(x -x c ) + (y -y c ). Then d T (a, b) ≤ d T (a, c) + d T (c, b) ≤ x c + y c + (1 + √ 2)(x -x c ) + (y -y c ) ≤ (1 + √ 2)x + y
In the second case, since x -x c < y -y c , by induction we have that

d T (c, b) ≤ (1 + √ 2)(y - y c ) + (x -x c ). Then, because y < x, d T (a, b) ≤ d T (a, c) + d T (c, b) ≤ x c + y c + (1 + √ 2)(y -y c ) + (x -x c ) ≤ (1 + √ 2)x + y Case 2: The interior of R(a, b) is empty. If no square S 1 , S 2 , . . . , S k is inductive, d T (a, b) ≤ (1 + √ 2)
x + y by Lemma 6. Otherwise, let S i be the first inductive square in the sequence and suppose that h i is the inductive point of S i . By Lemma 7, there is a j, i ≤ j ≤ k, such that h i , h i+1 , h i+2 , . . . , h j is a path in T of length at most (x h j -x h i ) + (y h i -y h j ) and such that x -x h j ≥ y h j -y ≥ 0. Since h j is closer to b, using the L ∞ -metric, than a is, we can apply induction to bound d T (h j , b). Putting all this together with Lemma 6, we get:

d T (a, b) ≤ d T (a, h i ) + d T (h i , h j ) + d T (h j , b) ≤ (1 + √ 2)x h i -(y h i -y) + (x h j -x h i ) + (y h i -y h j ) + (1 + √ 2)(x -x h j ) + (y h j -y) ≤ (1 + √ 2)x .
If l i is the inductive point of S i , by Lemma 7 there is a j, i ≤ j ≤ k, such that l i , l i+1 , l i+2 , . . . , l j is a path in T of length at most (x h j -x h i ) + (y h j -y h i ) and such that x -x h j ≥ y -y h j ≥ 0. Because the position of j with respect to b is good and since l j is closer to b, using the L ∞ -metric, than a is, we can apply induction to bound d T (l j , b). Putting all this together with Lemma 6, we get:

d T (a, b) ≤ d T (a, l i ) + d T (l i , l j ) + d T (l j , b) ≤ (1 + √ 2)x l i + y l i + (x l j -x l i ) + (y l j -y l i ) + (1 + √ 2)(x -x l j ) + (y -y l j ) ≤ (1 + √ 2)x + y .
What remains to be done is to prove Lemma 6. To do this, we need to develop some further terminology and tools. Let x i , for 1 ≤ i ≤ k, be the horizontal distance between point a and the E side of S i , respectively. We also set x 0 = 0.

Definition 8 A square S i has potential if d T (a, h i ) + d T (a, l i ) + d S i (h i , l i ) ≤ 4x i
where d S i (h i , l i ) is the Euclidean distance when moving from h i to l i along the sides of S i , clockwise.

Lemma 9 If R(a, b) is empty then S 1 has potential. Furthemore, for any 1 ≤ i < k, if S i has potential but is not inductive then S i+1 has potential.

Proof. If R(a, b) is empty then, by Lemma 4, a lies on the W side of S 1 and x 1 is the side length of square S 1 . Also, h 1 lies on the N or E side of S 1 , and l 1 lies on the S or E side of S 1 . Then d T (a, h 1 ) + d T (a, l 1 ) + d S 1 (h 1 , l 1 ) is bounded by the perimeter of square S 1 which is 4x 1 . Now assume that S i , for 1 ≤ i < k, has potential but is not inductive. Squares S i and S i+1 both contain points l i and h i . Because S i is not inductive, edge (l i , h i ) must be steep and thus d x (l i , h i ) < d y (l i , h i ). To simplify the arguments, we assume that l i is to the W of h i , i.e., x l i < x h i . The case x l i > x h i can be shown using equivalent arguments.

Since T i = △(h i-1 , h i , l i-1 = l i ) or T i = △(h i-1 = h i , l i-1 , l i )
, there has to be a side of S i between the sides on which l i and h i lie, when moving clockwise from l i to h i . Using the constraints on the position of h i and l i within S i from Lemma 4 and using assumptions that (l i , h i ) is steep and that x l i < x h i , we deduce that l i must be on the S side and h i must be on the N or E side of S i .

If h i is on the N side of S i then, because x l i < x h i , h i must also be on the N side of S i+1 and either l i is on the S side of S i+1 and

d S i+1 (h i , l i ) -d S i (h i , l i ) = 2(x i+1 -x i ) (1)
as shown in Figure 4a) or l i is on the W side of S i+1 , in which case

d S i+1 (h i , l i ) -d S i (h i , l i ) ≤ 4(x i+1 -x i ) (2)
as shown in Figure 4b).

If h i is on the E side of S i then, because x i+1 > x i (since (l i , h i ) is steep), h i must be on the N side of S i+1 and either l i is on the S side of S i+1 and inequality (1) holds or l i is on the W side of S i+1 and inequality (2) holds, as shown in Figure 4c).

Since S i has potential, in all cases we obtain:

d T (a, h i ) + d T (a, l i ) + d S i+1 (h i , l i ) ≤ 4x i+1 . (3)
Assume T i+1 = △(h i , h i+1 , l i = l i+1 ); in other words, (h i , h i+1 ) is an edge of T with h i+1 lying somewhere on the boundary of S i+1 beween h i and l i , when moving clockwise from h i to l i . By the triangular inequality, d 2 (h i , h i+1 ) ≤ d S i+1 (h i , h i+1 ) and we have that:

d T (a, h i+1 ) + d T (a, l i+1 ) + d S i+1 (h i+1 , l i+1 ) ≤ d T (a, h i ) + d T (a, l i ) + d 2 (h i , h i+1 ) + d S i+1 (h i+1 , l i ) ≤ d T (a, h i ) + d T (a, l i ) + d S i+1 (h i , l i ) ≤ 4x i+1 . S i S i+1 h i l i ∆ x S i S i+1 h i l i ∆ x S i S i+1 h i l i ∆ x a) b) c)
Figure 4: The first, second and fourth case in the proof of Lemma 9. In each case, the difference

d S i+1 (h i , l i ) -d S i (h i , l i ) is shown to be at most 4∆ x , where ∆ x = x i+1 -x i .
Thus S i+1 has potential. The argument for the case when

T i+1 = △(h i = h i+1 , l i , l i+1 ) is symmetric. Definition 10 A vertex c (h i or l i ) of T i is promising in S i if it lies on the E side of S i . Lemma 11 If square S i has potential and c = h i or c = l i is a promising point in S i then d T (a, c) ≤ 2x c . Proof. W.l.o.g., assume c = h i . Since h i is promising, x c = x h i = x i . Because S i has potential, either d T (a, h i ) ≤ 2x h i or d T (a, l i ) + d S i (l i , h i ) ≤ 2x h i .
In the second case, we can use edge (l i , h i ) and the triangular inequality to obtain d T (a,

h i ) ≤ d T (a, l i ) + |l i h i | ≤ 2x h i .
Here we define the maximal high and minimal low path.

Definition 12

• If h j is promising in S j , the maximal high path ending at h j is simply h j ; otherwise, it is the path h i , h i+1 , . . . , h j such that h i+1 , . . . , h j are not promising and either i = 0 or h i is promising in S i .

• If l j is promising in S j , the maximal low path ending at l j is simply l j ; otherwise, it is the path l i , l i+1 , . . . , l j such that l i+1 , . . . , l j are not promising and either i = 0 or l i is promising in S i .

Note that by Lemma 4, all edges on the path h i , h i+1 , . . . , h j are WN edges and thus the path length is bounded by (x h j -x h i ) + (y h j -y h i ). Similarly, all edges in path l i , l i+1 , . . . , l j are WS edges and the length of the path is at most (x l j -x l i ) + (y l i -y l j ).

We now have the tools to prove Lemma 6.

Proof of Lemma 6. If R(a, b) is empty then, by Lemma 4, b is promising. Thus, by Lemma 9 and Lemma 11, if no square S 1 , . . . , S k is inductive then d

T (a, b) ≤ 2x < (1 + √ 2)x + y.
Assume now that there is at least one inductive square in the sequence of squares S 1 , . . . , S k . Let S j be the first inductive square and assume, for now, that h j is the inductive point in S j . By Lemma 9, every square S i , for i < j, is a potential square.

Since (l j , h j ) is gentle, it follows that d 2 (l j , h j ) ≤ √ 2(x h j -x l j ). Let l i , l i+1 , . . . , l j-1 = l j be the maximal low path ending at l j . Note that d T (l i , l j ) ≤ (x l j -x l i ) + (y l i -y l j ). Either l i = l 0 = a or l i is a promising point in potential square S i ; either way, by Lemma 11, we have that d T (a, l i ) ≤ 2x l i . Putting all this together, we get d T (a, h j ) + (y h j -y) ≤ d T (a, l i ) + d T (l i , l j ) + d 2 (l j , h j ) + y h j ≤ 2x l i + (x l j -x l i ) + (y l i -y l j ) + √ 2(x h j -x l j ) + y h j ≤ √ 2x h j + x l j + y h j -y l j

≤ (1 + √ 2)x h j
where the last inequality follows x l j + y h j -y l j ≤ x h j , i.e., from the assumption that edge (l j , h j ) is gentle.

If, instead, c = l j is the inductive point in inductive square S j , let h i , h i+1 , . . . , h j-1 = h j be the maximal high path ending at h j . Then d T (h i , h j ) ≤ (x h j -x h i ) + (y h j -y h i ). Just as in the first case, we have that d T (a, h i ) ≤ 2x h i and d T (a, l j ) -y l j ≤ d T (a, h i ) + d T (h i , h j ) + d 2 (h j , l j ) -y l j ≤ 2x h i + (x h j -x h i ) + (y h j -

y h i ) + √ 2(x l j -x h j ) -y l j ≤ √ 2x l j + x h j + y h j -y l j ≤ (1 + √ 2)x l j .
where the last inequality follows from x h j + y h j -y l j ≤ x l j , i.e., from the assumption that (h j , l j ) is gentle.

Conclusion and perspectives

The L 1 -Delaunay triangulation is the first type of Delaunay triangulation to be shown to be a spanner [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF]. Progress on the spanning properties of the TD-Delaunay and the classical L 2 -Delaunay triangulation soon followed. In this paper, we determine the precise stretch factor of an L 1 -and L ∞ -Delaunay triangulation and close the problem for good. The techniques we develop in this paper have potential to be successfully applied to Delaunay triangulations defined by other regular polygons, and possibly even to the classical Delaunay triangulation.

From a routing perspective, it is of interest to construct routes in geometric graphs that can be determined locally from a neighbor's coordinates only [START_REF] Bose | Bounding the locality of distributed routing algorithms[END_REF]. Unfortunately, the route that is implicitely constructed in our proof is built using non-local decisions. It would be interesting to know whether in the L 1 -Delaunay triangulation a route with stretch 4 + 2 √ 2 can be constructed using a local routing algorithm. For TD-Delaunay triangulations, [START_REF] Bose | Competitive routing in the half-θ 6 -graph[END_REF] showed that there is no local routing algorithm that achieves a stretch that is less than 5/ √ 3 ≈ 2.88, whereas the stretch factor is actually 2. We leave open the questions regarding the gap between the stretch factor of L 1 -Delaunay triangulations and the stretch that is possible using local routing.

  points are placed on line segment [ac 1 ] and another k on line segment [c 2 b] in such a way that the difference in y coordinates between successive points on a segment is δ, as shown in Figures 1. (W.l.o.g. assume that √ 2

  y where d T (a, b) denotes the distance between a and b in triangulation T . Corollary 3 The stretch factor of the L 1 -and the L ∞ -Delaunay triangulation on a set of points P is at most 4 + 2 √ 2 ≈ 2.6131259 . . . Proof. By Theorem 2, an upper-bound of the stretch factor of an L ∞ -Delaunay triangulation is the maximum of the function (1 + √ 2)x + y x 2 + y 2

Case 1 :Figure 3 :

 13 Figure 3: Partition of R(a, b) into three regions in Case 1 of the proof of Theorem 2.

Table 1 :

 1 then continued on Key stretch factor upper bounds (optimal values are bold).

	Paper	Graph	Stretch factor
	[DFS87] [KG92]	L 2 -Delaunay L 2 -Delaunay	π(1 + 4π/(3 √ 5)/2 ≈ 5.08 √ 3) ≈ 2.41
	[Xia11]	L 2 -Delaunay	1.998
	[Che89] [Che86] [this paper]	TD-Delaunay L 1 -,L ∞ -Delaunay L 1 -,L ∞ -Delaunay	2 10 ≈ 3.16 √ 4 + 2 √ 2 ≈ 2.61

* Member of the "Institut Universitaire de France". Supported also by the ANR project "ALADDIN". † Supported by a Fulbright Aquitaine Regional grant and a DePaul University research grant.


Eric Lichtfouse
email: eric.lichtfouse@dijon.inra.fr

C-dating, the first method to calculate the relative age of molecular substance homologues in soil

Keywords: Soilorganicmatter, Humin, 13 C, Csequestration, Maizewax n-alkane, Agriculture, Datingmethod, Physicalsequestration, Encapsulation, Pollutants, Pharmaceuticals, Foodscience

This article reports the design of 13 C-dating, the first method to calculate the relative age ofmolecular substance homologues occurring in fractions from the same soil sample. Soil is a major carbon pool impacting modern climate by CO 2 release and uptake.Molecular substances that sequester carbon in soils are poorly known due to the absence of methodsto study molecular-level C dynamics over agricultural time scales, e.g. 0-200 years. Here I design a method to calculate the relative age of the plant-derivedC 31 n-alkane occurring in 6 fractions from a soil sample naturally 13 C-labelled by maize cropping during 23 years. Soil fractions arethe bulk soil extract, two humin-encapsulated fractions and threeparticle-size fractions.Results show that C 31 n-alkane homologueshave relative ages ranging from -6.7 years for the humin-encapsulated homologue to +25.1 years for the 200-2000 m fraction homologue. Such a wide variationof 31.8 years evidences temporal pools of molecular substances in soil. This finding also reveals that physical encapsulation can strikingly change the dynamics of a single molecular substance. 13 C-datingthus allowsto assess the carbon storage potential of molecular substances from crop soils. Such knowledge will help to identify molecular compounds, associated soil pools and agricultural practices that favour carbon sequestration. 13 C-dating is further applicable to any environmental sample containing organic matter subjected to a 13 C isotope shift with time. 13 C-dating will also help to study the sequestration and delayed release of chemicals in various disciplines, such as pollutants in environmental sciences, pharmaceuticals in medicine, and nutrients in food science.

Introduction

Molecular issues

Soil is a major carbon pool impacting climate change by CO 2 release and uptake [START_REF] Lal | Soils as source and sink of environmental carbon dioxide[END_REF][START_REF] Stavi | Challenges and Opportunities of Soil Organic Carbon Sequestration in Croplands. In Lichtfouse E (ed) Biodiversity, Biofuels, Agroforestry and Conservation Agriculture[END_REF][START_REF] Lichtfouse | Sustainable Agriculture[END_REF][START_REF] Lal | Soils as source and sink of environmental carbon dioxide[END_REF], 2011). Agricultural practices can either sequester or deplete soil carbon in the long run [START_REF] Benbi | A 25-year record of carbon sequestration and soil properties in intensive agriculture[END_REF][START_REF] Hazarika | Effect of tillage system and straw management on organic matter dynamics[END_REF][START_REF] Doumbia | Sequestration of organic carbon in West African soils by Aménagement en Courbes de Niveau[END_REF][START_REF] Halberg | Impact of organic pig production systems on CO 2 emission, C sequestration and nitrate pollution[END_REF][START_REF] Novak | Greenhouse gases and ammonia emissions from organic mixed crop-dairy systems: a critical review of mitigation options[END_REF][START_REF] Pati | Non-isotopic and 13 C isotopic approaches to calculate soil organic carbon maintenance requirement[END_REF], Lichtfouse et al., 2011).Geoengineering using for instance biochar addition to soil is a potential technique to sequester soil carbon and in turn decrease atmospheric CO 2 levels [START_REF] Sohi | A review of biochar and its use and function in soil[END_REF]. However mechanisms that control carbon sequestration are not fully understood because knowledge of thedynamics ofmolecularsubstances occurring in dead organic matter is scarce [START_REF] Marschner | How relevant is recalcitrance for the stabilization of organic matter in soils?[END_REF]. Dead matter indeed contain very complex mixtures of organic substancesinherited from the decay of living matter over short to long time periods [START_REF] Schnitzer | Soil organic matter -the next 75 years[END_REF][START_REF] Hedges | The molecularly-uncharacterized component of nonliving organic matter in natural environments[END_REF][START_REF] Ohkouchia | Compound-specific radiocarbon dating of Ross Sea sediments: A prospect for constructing chronologies in high-latitude oceanic sediments[END_REF]. In soils, although 14 C-dating of bulk carbon [START_REF] Wan | Radiocarbon dating of soil organic matter[END_REF] suggests the existence of organic substances agedup to several thousand years, dynamics at the molecular level are poorly known [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF][START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF], Lichtfouse et al., 1998a,b,Hedges and Oades, 1997[START_REF] Bull | Organic geochemical studies of soils from the Rothamsted classical experiments-V. The fate of lipids in different long-term experiments[END_REF][START_REF] Gleixner | Molecular dynamics of organic matter in a cultivated soil[END_REF][START_REF] Wiesenberg | Source and turnover of organic matter in agricultural soils derived from n-alkane/n-carboxylic acid compositions and C-isotope signatures[END_REF][START_REF] Freier | Mathematical modeling of soil carbon turnover in natural Podocarpus forest and Eucalyptus plantation in Ethiopia using compound specific δ 13 C analysis[END_REF][START_REF] Rubino | Carbon input belowground is the major C flux contributing to leaf litter mass loss: Evidences from a 13 C labelled-leaf litter experiment[END_REF]. Such knowledge would help to define agricultural and land management practices that will favour carbon sequestration and, in turn, offset global warming.

Sequestration in temporal pools

Sequestration of an individual substance in different pools of a same sample is a poorly known phenomenon despite major potential implications for pollutant bioavailability and plant nutrient release (Figure 1) [START_REF] Kubicki | Models of natural organic matter and interactions with organic contaminants[END_REF]Apitz, 1999, Sutton and[START_REF] Sutton | Molecular structure in soil humic substances: the new view[END_REF]. Given the extreme complexity of the soil matrix, individual substance homologues may indeed occur in the same soil sample within different physical and temporal pools, and thus canhave various ages and turnovers [START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF]. For instance a free substance should be younger than the bound homologue encapsulated in humin, the macromolecular organic network of soils. A such hypothesis stems from reports showing for example the unexpected preservation of proteins in sediments [START_REF] Knicker | Survival of protein in an organic-rich sediment: possible protection by encapsulation in organic matter[END_REF]. The existence of temporal pools of molecular substances is of fundamental importance to understand the mechanisms of carbon cycling at the molecular level. The existence of temporal pools is also of applied importance to identify which individual substances and associated pools contribute to carbon sequestration. A suitable method is therefore necessary to assess the relative age of individual substances.

Figure 1. Encapsulation of molecular organic substances in soil. This scheme shows the consequences of physical encapsulation on the behaviour of organic substance homologues. Such consequences are relevant for carbon sequestration, plant nutrient storage and long-term pollutant release in waters, for example. The concept of encapsulation is also relevant for the delayed release of encapsulated pharmaceuticals and food substances (Mishra et al., 2010, Fang and[START_REF] Fang | Encapsulation of polyphenols -a review[END_REF].

Fractions

 [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF][START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF], Lichtfouse et al. 1998b[START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. A possible pyrolytic carbon contribution to the humin-encapsulated C 31 nalkane released by pyrolysis (b) can be excluded as explained previously (Lichtfouse et al. 1998a,b). Indeed gas chromatography analysis of the pyrolysate alkane/alkene fraction show that C 27 -C 33 n-alkanes have a strong odd-number predominance, typical of plant waxes, without n-alk-1-ene homologues typical of pyrolytic products (Lichtfouse et al. 1998a). Whereas C 11 -C 26 show no odd/even predominance and have n-alk-1-ene homologues typical of pyrolytic products. In other words, pyrolysis is a means to release compounds that are physically encapsulated, that is without strong chemical bonds. Here the trick is to find a means to distinguish pyrolytic versus encapsulated homologues. Dating at the molecular level 14 C-dating can date organic matter agedfrom hundreds to thousands of years, and has been successfully applied at the molecular level in sediments [START_REF] Pearson | The origin of n-alkanes in Santa Monica Basin surface sediment: a model based on compound-specific Δ14C and δ13C data[END_REF][START_REF] Pearson | Origins of lipid biomarkers in Santa Monica Basin surface sediment: a case study using compound-specific Δ 14 C analysis[END_REF][START_REF] Ohkouchia | Compound-specific radiocarbon dating of Ross Sea sediments: A prospect for constructing chronologies in high-latitude oceanic sediments[END_REF].Nonetheless 14 C-dating is less suitable to study the turnover of organic matter over short time periods relevant to agriculture and climate change, e.g. from 0 to 200 years. This issue is due both to the global 14 C contamination of modern samples by atomic bomb testing around 1950 [START_REF] Harkness | The temporal distribution of 'bomb' 14 C in a forest soil[END_REF] and to the higher standard deviation of 14 C-dating versus the rapid turnover of recent organic material in soils [START_REF] Trumbore | Age of soil organic matter and soil respiration: radiocarbon contraints on belowground C dynamics[END_REF]. Alternatively, 14 C-spiking of tagged compounds is another technique used for instance to study pesticide biodegradation [START_REF] Barriuso | Formation of pesticide nonextractable (bound) residues in soil: magnitude, controlling factors and reversibility[END_REF]. However 14 C-spiking is less representativeof native compounds because spiking in itself does not represent the natural behaviour of native compounds such as plant-derived substances found in crop soils. Therefore a method is needed to assess the dynamics of individualsoil organic substances over short time periods. Here I report a novel method, named 13 C-dating, designed by conceptualisingprevious findings [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF][START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF], Lichtfouse et al. 1998b[START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. 13 C-dating allows to measure the relative age of organic substances from dead organic matter that has been 13 C-labelled at natural abundance.

Experimental

Detailed experimental procedures and data are given elsewhere [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF][START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF], Lichtfouse et al. 1998b[START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. Briefly, soils were sampled in an experimental maize crop field in France. Cropping maize, a naturally 13 C-enriched plant, is a means to follow the fate of plant carbon into soil organic matter. In this article I discuss data from a soil sample cultivated 23 years with maize. The C 31 soil nalkane, a compound derived from plant waxes, was analysed in 6fractionsfrom the same soil sample.

Fractions are the bulk soil extract; the humin-encapsulated n-alkane fraction released either by extraction or pyrolysis; and n-alkanes in 0-50 m, 50-100 m, and 200-2000 m particle-size fractions (Figure 2).

The bulk soil extract was obtained by CHCl 3 -MeOH 3/1 (v/v) extraction,then was fractionated by several steps of silica gel chromatography to yield an alkane fraction suitable for 13 C analysis [START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF].

Humin was obtained by treatment of the CHCl 3 -MeOH pre-extracted soil sample by HF/HCl to remove minerals (Lichtfouse et al., 1998b). Two pools of encapsulated alkanes were isolated from humin: a pool of alkanes occurring in the CHCl 3 -MeOH humin extract, and a pool released by pyrolysis of the CHCl 3 -MeOH pre-extracted humin. Particle-size fractions were isolated from the soil sample by sieving in water followed by density separation [START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. Alkane fractions were obtained from particle-size fractions by CHCl 3 -MeOH extraction followed by several steps of silica gel chromatography. Alkane fractions were then analysed for  13 C values by gas chromatography-combustion-isotope ratio mass spectrometry (GC-C-IRMS). I reviewed the main applications of compound specific isotope analysis [START_REF] Lichtfouse | Compound-specific isotope analysis (CSIA). Application to archaeology, biomedical sciences, biosynthesis, environment, extraterrestrial chemistry, food science, forensic science, humic substances, microbiology, organic geochemistry, soil science and sport[END_REF].

Results and discussion

Turnover of soil molecular substances

The principle of 13 C-dating at the molecular level is built on previous datafrom 13 C-labelling cultivation experiments [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF][START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF], Lichtfouse et al. 1998b[START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. Specifically, cropping maize, a naturally 13 C-enriched C 4 plant, on soils previously cultivated with naturally 13 C-depleted C 3 plants, e.g. wheat, slowly incorporates 13 C-enriched plant matter in soil (Figure 3). As a consequence the C 31 maize leaf wax n-alkane of  13 C -20.6‰ is progressively introduced into the soil and mix with the 13 C-depleted C 31 soil n-alkane of  13 C -35.7‰. The  13 C value of soil C 31 n-alkane thus increases from -35.7‰ to -28.1‰ after 23 years of maize cropping [START_REF] Lichtfouse | [END_REF]. A such isotope shift allows to calculate the percentage of maize-derived carbon within the soil C 31 n-alkane:

Equation 1 M = 100.( - 0 )/( m - 0 )
Where M isthe percentage of maize-derived C in the soil substance,  denotes the 13 C value of the soil substance at a given time of maize cultivation,  0 depicts the 13 C value of the soil substance before maize cultivation (-35.7‰), and  m refers to the 13 C value of the maize substance (-20.6‰). This calculation shows that the soil C 31 n-alkane contains 50.3% of maize-derived carbon after 23 years of calculation. Therefore about half of the soil C 31 n-alkane is renewed after 23 years.The dynamics of the soil C 31 n-alkane can be further modelledusing a first-order kinetic law [START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF]:

Equation 2 M = 100 x (1 -exp(-0.031t 1 ))

Where M refers to the percentage of maize-derived C in the soil substance and t 1 denotes the time of maize cultivation in years. Accordingly the complete renewal of 99%of the soil C 31 n-alkane will last 148 years. This finding represented the first determination of the turnover of soil carbon at the molecular level [START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF]). The isotope value of the soil n-alkane therefore increases over years of maize cultivation [START_REF] Lichtfouse | [END_REF].

Physical encapsulation of substance homologues

Access to the turnover further allows to measure the relative age of substance homologues occurring in 6fractions from the same soil sample (Figure 2). The free C 31 n-alkane is isolated from the bulk soil by solvent extraction [START_REF] Lichtfouse | [END_REF][START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF]. The encapsulatedC 31 n-alkane homologue is isolated from humin either by extraction or pyrolysis (Lichtfouse et al. 1998b[START_REF] Lichtfouse | Temporal pools of individual organic substances in soil[END_REF]. C 31 n-alkane homologues are also extracted from soil particle-size fractions [START_REF] Cayet |  13 C of plant-derived n-alkanes in soil particle-size fractions[END_REF]. Previous occurrence of substance homologues in compartments of soils and modern sediments were suspected but not proven due to the lack of method allowing to distinguish compounds of identicalmolecular structure. This issue is solved here by measuringdifferent 13 C isotope ratios for C 31 n-alkane homologues occurring in 6fractions from a soil cultivated 23 years with maize (Figure 2).

Results show a wide range of C 31 n-alkane  13 C values from -29.7‰ for the humin encapsulated homologue to -24.0‰ for the homologue in the 200-2000 m particle-size fraction. As a consequence the oldest C 31 nalkane homologue is encapsulated into humin and contains only 39.74% of maize C, whereas the youngest C 31 n-alkane homologue occurs in the 200-2000 m particle-size fraction and contains 77.48% of maize C. Such a large difference demonstrate unambiguously for the first time that the turnover of an individual substance vary widely depending on its physical localisation within the soil matrix. This finding implies also that the stability and degradation of substances is soils cannot be explained solely by their molecular structure, but should take physical protection into account. Physical encapsulation of organic molecules was previously hypothesised but definitive proof was lacking. Here the lower maize-C content of n-alkane homologues evidence the mechanism of physical encapsulation at the molecular level.

A possible effect of biodegradation on the 13 C-dating method should be considered. Indeed, in theory, free compounds should be more accessible to microbes and should thus be more biodegraded that bound compounds. If biodegradation occurs, then the  13 C values may be changed if biodegradation induces 13 C/ 12 C isotope fractionation. However petroleum biodegradation experiments using microbial communities show the absence of  13 C shift of alkanes [START_REF] Mazeas | Absence of stable carbon isotope fractionation of saturated and polycyclic aromatic hydrocarbons during aerobic bacterial biodegradation[END_REF]. A further comparison of petroleum samples of increasing degree of biodegradation also shows the absence of 13 C isotope shifts of n-alkanes [START_REF] Sun | Stable carbon and hydrogen isotopic fractionation of individual n-alkanes accompanying biodegradation: evidence from a group of progressively biodegraded oils[END_REF]. In addition a 23-year decomposition experiment of Calluna vulgaris shoots using litter-bags buried in a peat bog shows the absence of  13 C shifts of n-alkanes despite 90% weight loss of the plant shoot biomass [START_REF] Huang | Absence of carbon isotope fractionation of individual n-alkanes in a 23-year field decomposition experiment with Calluna vulgaris[END_REF]). To conclude, a possible effect of biodegradation on the 13 C-dating method due to a 13 C shift can be reasonably excluded for the results of this article.

Relative age

The relative age of C 31 n-alkane homologues occurring in different fractions from the same soil can be calculated according to:

Equation 3 Relative age = t 1 -t 2
Where t 1 refers to the time of maize cultivation calculated using kinetics of maize C content in the free C 31 nalkane from the bulk soil (Equation 2). 1999).The wide age difference of 31.8 years between the two n-alkane fractions reveals that physical encapsulation can strikingly change the dynamics of a molecular substance. To conclude, 13 C-dating is a novel method to calculate the relative age of organic substance homologues in soils. [START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF]. Note that the C 31 nalkane encapsulated in humin is 6.7 years younger than the C 31 n-alkane in the bulk soil extract. Note also that the C 31 n-alkane from the 200-2000 m particle-size fraction is 25.1 years younger than the C 31 n-alkane in the bulk soil extract. Those findings demonstrate both physical encapsulation and the occurrence of temporal pools at the molecular level. The wide age difference of 31.8 years between the two n-alkane fractions reveals that physical encapsulation can strikingly change the dynamics of a molecular substance.

Implications 13 C-dating is a method requiring the occurrence of an isotope shift with time, either at natural abundance or by 13 C-labelling. This method is particularly useful over short-time periods of 0-200 years where 14 C-dating is less suitable. 13 C dating is applicable to study individual substances from complex media such as soils, palaeosols, sediments, sewage sludge's, and organic matter from waters and airborne particulates. Noteworthy, 13 C dating should not be used to measure absolute ages because 13 C dating is based on kinetic modelling. Concerning climate change 13 C-dating should be particularly useful to identify molecular compounds and associatedfractions that sequester carbon over decades to centuries. A such knowledge would indeed help to define sustainable agricultural systems that are sequestrating carbon. 13 C-dating can also be applied to study the mechanisms of pollutant trapping in complex environmental samples (Lichtfouse et al., 1998b). Such knowledge would be useful to understand for example why herbicides are still released in waters years after the herbicide ban [START_REF] Barth | Mobility, turnover and storage of pollutants in soils, sediments and waters: achievements and results of the EU project AquaTerra. A review[END_REF]. Understanding pollutant trapping at the molecular level is also needed to define agricultural practices that reduce the use of pesticides [START_REF] Alletto | Tillage management effects on pesticide fate in soils. A review[END_REF]. 13 C dating can also be used to study the turnover of substances in biological samples [START_REF] Lichtfouse | Compound-specific isotope analysis (CSIA). Application to archaeology, biomedical sciences, biosynthesis, environment, extraterrestrial chemistry, food science, forensic science, humic substances, microbiology, organic geochemistry, soil science and sport[END_REF]. For instance this non-radioactive technique would allow to investigate the metabolism of naturally 13 C-enriched maize-derived food substances or 13 C-tagged pharmaceuticals and food substances in the human body and other living organisms. Indeed the concept of encapsulation is highly relevant to medicine and food science (Mishra et al., 2010, Fang and[START_REF] Fang | Encapsulation of polyphenols -a review[END_REF].

Conclusion

13 C-dating allows to calculate the relative age of substance homologues occurring in various pools from the same sample. Results show large variations from -6.7 to +25.1 years of the relative age of the C 31 n-alkane in 6 fractions from the same soil sample. Such wide age difference of 31.8 years reveals that physical encapsulation can strikingly change the dynamics of a molecular substance. 13 C-dating will thus be useful to identify substances and associated fractions that sequester carbon in soils. 13 C-dating is potentially applicable to study the dynamics of organic substances occurring in complex media subjected to an isotope shift over time, such as sediments, water, sludge's, airborne particulates and biological samples. 13 C-dating is also potentially applicable to study the delayed release of molecular substances in medicine and food science.

Figure 2 .

 2 Figure 2. Top: fractionation of a soil sample into 6 fractions containing plant-derived n-alkanes. Bottom: relative age of soil C 31 n-alkane homologues

Figure 3 .

 3 Figure 3. Labelling individual soil organic compounds at natural abundance.Maize (Zea mays), a naturally 13 C-enriched plant, is cultivated on a soil which was previously cultivated with 13 C-depleted plants. The C 31 leaf wax n-alkane of  13 C -20.6‰, is progressively introduced into the soil and mix with the 13 C-depleted C 31 soil n-alkane ( 13 C -35.7‰).The isotope value of the soil n-alkane therefore increases over years of maize cultivation[START_REF] Lichtfouse | [END_REF].

  t 2 denotes the time of maize cultivation of the soil sample, of 23 years in our example (Figure 2). In other words t 1 represents the cultivation time at which the C 31 n-alkane from soil fractions, e.g. humin-encapsulated and particle sizes, would have the same maize C content as the free C 31 n-alkane from the bulk soil extraction (see arrows inFigure 4). For instance the humin-encapsulated C 31 nalkane from the soil cultivated 23 years with maize has a maize C content equal to free homologue from the soil cultivated 16.3 years, thus yielding a relative age of -6.7 years. Similarly the C 31 n-alkane from the 200-2000 m particle-size fraction of the soil cultivated 23 years with maize has a maize C content equal to free homologue from the soil cultivated 48.1 years, thus yielding a relative age of +25.1 years. Those findings bring unambiguous evidence for temporal pools of individual substance homologues in soil(Lichtfouse

Figure 4 .

 4 Figure 4. Principle of13 C-dating calculation of the relative ages of C 31 n-alkane homologues in two soil compartments, the humin-encapsulated and the 200-2000 m particle-size fraction, from a soil cultivated 23 years with maize. The kinetic curve refers to equation 2[START_REF] Lichtfouse | Heterogeneous turnover of molecular organic substances from crop soils as revealed by 13 C labeling at natural abundance with Zea mays[END_REF]. Note that the C 31 nalkane encapsulated in humin is 6.7 years younger than the C 31 n-alkane in the bulk soil extract. Note also that the C 31 n-alkane from the 200-2000 m particle-size fraction is 25.1 years younger than the C 31 n-alkane in the bulk soil extract. Those findings demonstrate both physical encapsulation and the occurrence of temporal pools at the molecular level. The wide age difference of 31.8 years between the two n-alkane fractions reveals that physical encapsulation can strikingly change the dynamics of a molecular substance.


M.D. Matteo Gelardi
email: gelardim@inwind.it

MD Giovanni Passalacqua

MD Maria Luisa Fiorella

Adriana Mosca Bsc

MD Nicola Quaranta

Nasal cytology: the " infectious spot ", an expression of a morphological-chromatic biofilm

Keywords: nasal cytology, Biofilms, Infectious Spot, infectious rhinitis, nasal mucosa

The purpose of study was to describe some "morphological-chromatic" patterns (i.e.spots of cyan colour) identified during the study of nasal cytology in patients with both bacterial and fungal infectious rhinological disorders. These peculiar aspects strongly suggest the presence of a microscopic biofilm. We retrospectively examined 1,410 nasal cytology specimens from subjects who underwent clinical-instrumental investigations (history, ENT visit, nasal endoscopy and nasal cytology) from January to August 2010. The control samples were represented by 30 subjects not suffering from infectious rhinological diseases. The presence of particular spots of "Cyan", was found in colour in 107/1,410 rhinocytograms (7.6 %) within which bacterial colonies and/or fungal spores were found.

We called these colored spot formations "Infectious Spots" (IS).

2

The positivity to PAS staining confirmed the polysaccharide nature of the colored spots and allowed us to relate them to biofilms. This study demonstrates, for the first time, that nasal cytology performed by optical microscope can play an important role in detecting biofilms.

Introduction

Over the last years nasal cytology is increasingly used in the study of either allergic and vasomotor rhinological disorders, or infectious and inflammatory rhinitis [START_REF] Bogaerts | The diagnostic value of a cytogram in rhinopathology[END_REF][START_REF] Malmberg | Nasal smear as a screening test for immediate-type nasal allergy[END_REF]. Since nasal cytology can detect cellular changes of epithelium exposed to physical-chemical inflammation [START_REF] Glück | Cytopathology of the nasal mucosa in chronic exposure to diesel engine emission: a five-year survey of Swiss customs officers[END_REF][START_REF] Boysen | Nasal mucosa in workers exposed to formaldehyde: a pilot study[END_REF], acute or chronic infections of different nature (viral, bacterial, fungal or parasitic) [START_REF] Gelardi | Epstein-barr virus induced cellular changes in nasal mucosa[END_REF]6], it has been matter of interest, both in basic and clinical research.

Several reasons contributed to the increased interest in this diagnostic method: among them, the simplicity of the cytological technique and the lack of invasiveness, which makes possible to repeat the examination in the follow-ups and monitoring of therapy. The nasal cytology has characteristics suitable for its application in the biomedical and clinical research, outpatient care, and it can be performed on subjects of any age [7].

Over the years, several studies on nasal cytology helped to clarify some of the pathophysiological mechanisms underlying IgE-mediated rhinitis, as well as the identification of new classified entities such as non-allergic rhinitis with eosinophilia (nonallergic rhinitis with eosinophils , NARES), with mast cells (non-allergic rhinitis with mast cell, NARMA), neutrophilic forms (non-allergic rhinitis with neutrophils, NARNE) and, finally, the eosinophil-mast cell (non-allergic rhinitis with eosinophils and mast cell, NARESMA) [START_REF] Bickmore | Cytology of nasal secretions: further diagnostic help[END_REF][START_REF] Jacobs | Non-allergic rhinitis with eosinophilia (NARES syndrome): clinical and immunologic presentation[END_REF][10][START_REF] Gelardi | Non-allergic rhinitis with eosinophils and mast cells constitutes a new severe nasal disorder[END_REF].

Over the last decade, rhinological diagnosis has been devoted, to the possibility to relate chronic rhinopathies (rhinosinusitis, nasal polyps, adenoid hypertrophy, etc.) with the presence of biofilms [START_REF] Ferguson | Demonstration of biofilm in human bacterial chronic rhinosinusitis[END_REF][START_REF] Głowacki | Biofilm from patients with chronic rhinosinusitis. Morphological SEM studies[END_REF][START_REF] Psaltis | Confocal scanning laser microscopy evidence of biofilms in patients with chronic rhinosinusitis[END_REF][START_REF] Sanclement | Bacterial biofilms in surgical specimens of patients with chronic rhinosinusitis[END_REF][START_REF] Vlastarakos | Biofilms in ear, nose, and throat infections: how important are they?[END_REF].

The investigation of biofilms has increased its possibilities with the evolution of the methods of investigation, whereas the early work was based on scanning electron microscopy (SEM) [START_REF] Ganderton | Scanning electron microscopy of bacterial biofilms on indwelling bladder catheters[END_REF], and transmission electron microscopy (TEM) [18], which clarify the ultramicroscopic fine structure. Indeed electron microscopy and specific staining of polysaccharides with ruthenium identify the nature of the extracellular fibers as biofilms and their association with cells [19,[START_REF] Siebel | Observations of binary population biofilms[END_REF]. However, the solvents necessary for the gradual dehydration of the sample, is responsible for generating images of biofilms with artifacts. In the '90 the development of confocal laser scanning microscopy (CLSM) [START_REF] Palmer Rj | Modern microscopy in biofilm research: confocal microscopy and other approaches[END_REF] gave the possibility to examine biofilms in situ without limitations, although at a lower resolution, in comparison with SEM. Most of studies on biofilms currently available are aimed to understanding either the mechanisms of drug resistance systems [START_REF] Hoyle | Bacterial resistance to antibiotics: the role of biofilms[END_REF][23][START_REF] Davies | Understanding biofilm resistance to antibacterial agents[END_REF] in order to prevent contamination of medical devices (cochlear implants, cardiac valves, venous catheters, urinary catheters, contact lens, intrauterine devices, etc.) [START_REF] Tonnaer | Detection of bacteria in healthy middle ears during cochlear implantation[END_REF][START_REF] Dickinson | Infections associated with indwelling devices: infections related to extravascular devices[END_REF][START_REF] Schumm | Types of urethral catheters for management of short-term voiding problems in hospitalized adults: a short version Cochrane review[END_REF] or the pathophysiological mechanisms of major diseases (endocarditis, cystic fibrosis, chronic rhinosinusitis, otitis media, etc) [START_REF] Liu | Biofilms in pediatric respiratory and related infections[END_REF][START_REF] Mladina | Biofilm in nasal polyps[END_REF][30][START_REF] Post | The role of biofilms in otolaryngologic infections: update[END_REF]. This study describes ,for the first time, the significance of "morphological-chromatic" entities found during nasal cytology in patients with rhinological disorders.

Materials and Methods

From January to August 2010 we examined the nasal cytology of 1,410 subjects, 826 (58.5%) males, 584 (41.4%) females, aged between 2 and 74 years (average 32). All enrolled subjects underwent clinical-instrumental investigations (history, ENT visit, nasal endoscopy and nasal cytology).

Control sample

The control sample consisted of 30 subjects (12 males and 18 females) aged between 5 and 68 years (average 44), and admitted to hospital because of non-infectious diseases: voice disorders from chronic vocal abuse (4), tinnitus (6), neurosensorial hearing loss (9), trigeminal neuralgia [START_REF] Gelardi | Epstein-barr virus induced cellular changes in nasal mucosa[END_REF]; vertiginous syndromes secondary to cupololithiasis (6).

Nasal cytology

The nasal cytology was performed by anterior rhinoscopy, using a nasal speculum and good lighting. The collection technique consisted of scrapings from the middle portion of the inferior turbinate, using a Rhino-Probe ® [7]. Anesthesia was not necessary. In young and/or uncooperative patients cell sample was obtained by a nasal swab. Briefly, the cellular material was placed on a glass slide, fixed by air drying and then stained by the May-Grunwald Giemsa (MGG) method (Carlo Erba ® , Milan, Italy). MGG staining is the most widely used method in diagnostic nasal cytology, because all the cellular components of the nasal mucosa, from inflammatory cells (neutrophils, eosinophils, mast cells, lymphocytes) up to bacteria, spores, fungal hyphae, and mucous secretions are easly stained. Furthermore, to confirm the nature of the polysaccharide secretions present in the cytological preparations, a special staining method (PAS-Periodic Acid-Schiff) was used [START_REF] Nevalainen | Periodic acid Schiff (PAS) staining of eponembedded tissues for light microscopy[END_REF]. The slide was observed by a Nikon E600 light microscope (Nikon, Canada) equipped with a digital camera (Nikon "Coolpix 3:34") for the acquisition of microscopic images. For the rhinocytogram analysis, 50 microscopic fields were read at a magnification of 1000 x, to assess the presence of normal and abnormal cellular elements, along with any microscopic features (spots, special inclusions, etc.) important for the diagnosis. Cell counts, bacterial and fungal analysis, were carried out by a semi-quantitative grading, as proposed by Meltzer [START_REF] Meltzer | Nasal cytology in clinical practice[END_REF]. In particular, bacteria and fungal spore assessment was determined as follows: Grade 0 (not visible); Grade 2 + (moderate number); Grade 3 + (easily visible); Grade 4 + (many of which cover the entire field of view).

Results

Control group

Control group showed a normal nasal cytology, characterized by the presence of many hair cells and muciparous cells, at the typical ratio 4-5:1. Neither immune-inflammatory cells (eosinophils, mast cells etc.) with the exception of some neutrophils (Grade 1 +), nor items such as bacteria, spores and/or fungal hyphae (Grade 0) were observed. Specific structures and/or colour variations of doubtful significance were not found..

Study Group

193/1,410 (13.6%) rhinocytograms had cytological signs of infectious rhinitis, characterized, at a different degree from grade 1 + to 4 +, by inflammatory infiltration ( i.e. neutrophils, intra and extracellular bacteria, and/or fungal spores). In 107/1,410 (7.6%) rhinocytograms specific "Cyan" colour patches corresponding to a wavelength of 480 nanometers, were present (Fig. 1 a,b,c,d).

Since bacteria and/or fungal spores were observed within colour samples of different, size the possibility that these formations could be the expression of biofilm prompted us to perform a specific staining for polysaccharides. (ì.e. periodic acid staining -Schiff's reagent -PAS), which are the main constituents of the matrix of biofilm [34]. The positivity to PAS staining (Fig. 2) confirmed the polysaccharide nature of chromatic stains thus, confirming their association with biofilms. This morphological-chromatic expression was termed "infectious spot" (IS).

DISCUSSION

Already in 1600 Anton van Leeuwenhoek, scraping the surface of teeth, observed with his primitive microscope, the "animaluculae", which were nothing but microbial aggregates. It took many years of research with advanced diagnostic equipment to identify the chemical and genetic structure of these bacterial colonies, which were later named "biofilm". Thanks to electron microscope studies, we presently know that biofilm consists of bacterial colonies (around 15% of the volume), surrounded by an organic matrix produced by themselves, whose skeleton is composed of exopolysaccharides [34]. The amount of polysaccharides is variable, and tend to increase as the age of biofilms increases. Extracellular proteins and DNA have been also identified in the biofilm matrix. The physico-chemical nature of the biofilm, confer resistance to antimicrobial agents such as antibiotics, disinfectants and detergents. This is not a genetic antimicrobial resistance (i.e. carried by plasmids, or related to mutational events), but is rather due to the ability of individual cells inside the biofilm to differentiate into a phenotypically antibiotic tolerant state [START_REF] Drago | Activity of ceftibuten, cefaclor, azithromycin, clarithromycin, erythromycin and telithromycin against Streptococcus pyogenes clinical isolates with different genotypes and phenotypes[END_REF]. Other mechanisms intervene, including the delayed penetration of the antimicrobials through the matrix of the biofilm or the abnormal growth of organisms within the biofilm [START_REF] Donlan | Biofilms: survival mechanisms of clinically relevant microorganisms[END_REF][START_REF] Costerton | Bacterial biofilms: a common cause of persistent infections[END_REF]. On this ground, identification of biofilms has a not negligible clinical relevance also in rhinology [START_REF] Post | The role of biofilms in otolaryngologic infections: update[END_REF].

Nonetheless, the electron microscope techniques are expensive, poorly accessible and require special processing of samples, which can also result in artifacts. For this reason we attempted to identify biofilms in nasal mucosa, by means of nasal cytology, evaluating a large number of scrapings.

During the cytological study, in a large proportion of patients with infectious rhinitis, we repeatedly observed particular chromatic spots, which were variable in size, had irregular and blurred margins, and an intense cyan coloration (wavelength around 480 nm). Such colour attracted our attention, since this chromatic band does not fall in the colour spectrum of nasal cytology, when stained with MGG. In addition, the presence of bacteria or fungal spores, suggested that those spots (infectious spots) could be the optical microscopy expression of biofilm. Thus, when infectious spots were observed, a staining with PAS, which is polysaccharide-specific, was carried out. That staining resulted invariably positive when micro-organisms were present, thus we confirmed the biofilm-related nature of the infectious spots. Of note, the infectious spot, which always remain in the spectrum of the cyan color, may have variable shades. This is probably attributable to the age of biofilms, which when more mature is more rich in polysaccharides, and consequently has a more intense coloration.

Nasal cytology in infectious rhinological diseases, has been predominantly focused the presence or absence of bacteria in the planctonic state, which are known to represent only a small percentage (<10%) of bacterial biomasses in nature which, in contrast, are mostly organized in biofilms. The present study demonstrates for the first time that nasal cytology is able to identify biofilms in nasal scrapings, by a relatively simple and economic technique. In the light of these results, we are confident that the nasal cytology will find applications not only in experimental fields, but also in diagnosis and therapy of allergic and nonallergic rhinitis. Further comparative studies are, nonetheless, needed to validate our observations.

Fig 1 AFigure 2 A

 12 Fig 1 A,B,C,D: Spot infectious. Visible colonies of bacteria (a, c) or fungal spores (b, d) embedded in a brightly colored cyan matrix. Staining MGG -400 and 1000X magnification