Karen Miranda
email: kmiranda@correo.cua.uam.mx

Nathalie Mitton

Tahiry Razafindralambo

On the Impact of Routers' Controlled Mobility in Self-Deployable Networks

Keywords: substitution networks, self-deployment, controlled mobility

b) (c) BASE NETWORK + SUBSTITUTION NETWORK BASE NETWORK BASE NETWORK + FAILURE Fig. 1. Typical use case for a base network and a substitution network.

I. INTRODUCTION

A rapidly deployment network is a solution to provide communication services in disaster scenarios. Specifically, we focus on a wireless solution named the substitution networks. A substitution network is a temporary network to replace a portion of a damaged infrastructure (called hereafter base network) by means of mobile routers (called substitution routers) capable of moving on demand and connecting to the base network through bridge routers (Fig. 1a).

Bridge routers are connected in between the base and the substitution networks, and used to forward the traffic from the base network to the substitution network and vice versa.

Mobile substitution routers are wireless routers of the substitution network, possibly connected to bridge routers, and whose union provides alternative path(s) to the base network. Fig. 1 depicts the complete overview of using a substitution network, where the bridge routers are deployed together with the base network (Fig. 1a). In this example, the base network operates without the help of the mobile routers. When a failure occurs (Fig. 1b), the mobile routers are deployed. In this architecture, the failure detection and the deployment are done autonomously by the base network itself. Mobile routers try to find an optimal position to restore the connectivity service and to ensure quality of service (QoS) (Fig. 1c). In some cases, the continuous redeployment of the routers may be necessary to adapt to evolving network and QoS conditions (Figure 1d).

Particularly, our goal is to have an autonomous router deployment as well as a possible redeployment of the mobile routing devices. Therefore, it is necessary to design algorithms and protocols to deploy and re-deploy such devices. Since the routing devices are autonomously provided with a limited battery, it is also necessary to consider energy constraints during the deployment. Moreover, the deployment computation process does not consider a central entity in the network, hence, this process should be executed in a distributed manner. An efficient router/relay (mobile or static) deployment algorithm must take the link quality into account in order to decide when and where to deploy a relay. For that purpose, the deployment algorithms must be able to measure the wireless link quality. We have presented in a previous work the Adaptive POsitioning aLgOrithm (APOLO) [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF]. This paper presents the extended results of APOLO [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF] developed for substitution networks obtained under stress and some results under different assumptions, especially regarding channel states. The remaining of the paper is structured as follows. After browsing the literature (Sec. II), Section III describes the background and the basic concepts used in this paper. Then, Section IV recalls the proposed adaptive positioning algorithm (APOLO). Section V and Section VI present the simulation settings and results. Finally, we discuss these results and conclude in Section VII.

II. STATE OF THE ART

Mobile routers of a RDN perform the same tasks than their static similar distributing the data traffic, however, they must self-position in a given area. In literature, we find a few relative proposals. [START_REF] Reich | Connectivity Maintenance in Mobile Wireless Networks via Constrained Mobility[END_REF], presents the Spreadable Connected Autonomic Network algorithm in which the mobile routers move to expand the covered area. In order to maintain the connectivity, they are allowed to move as long as there is no risk of disconnection, if a possible disconnection is detected, the mobile router must stop moving. A different strategy is presented in [START_REF] Nguyen | Using Mobile Robots to Establish Mobile Wireless Mesh Networks and Increase Network Throughput[END_REF], where the mobile routers follow a leader router in a straight-line formation, once the leader reaches the objective point, it stops and the rest of the routers start stopping. These approaches differ from ours since they do not consider link quality.

III. PRELIMINARIES

We consider a wireless network composed of mobile routers that are located and may move on the two-dimensional Euclidean space. We use "node" as a generic term for any device in the simulation neighborhood, for instance, the mobile or classic routers. For the sake of simplicity, we assume that the transmission range R of a node u is the area in which another node v can receive/send messages from/to u, i.e., d(u, v) < R(u), where d(u, v) represents the Euclidean distance between u and v, and therefore, it exists a link X between u and v. We assume that two nodes are "neighbors" when they are within the communication range of each other.

In the following, we use X prev and X next to refer to the links of the previous and next hops, respectively, of a mobile router. Likewise, we assume that some of the devices are fixed, that traffic needs to be transferred between two fixed devices, and that the wireless routers dynamically move in the scenario and act as relays, regardless of the routing protocol. And, as many link layer protocols, we assume that each node is equipped with a timer and an 802.11 wireless card as well as with an identifier that is unique in the network (MAC address).

We define the quality of communication link, or just "link quality", as the probability that a message transmitted on the link is successfully received, that is, the reliability of the link [START_REF] Souryal | Rapidly-Deployable Mesh Network Testbed[END_REF]. The link quality can be assessed as a function of the received signal strength (RSS) or the signal-to-noise ratio (SNR) [START_REF] Baccour | F-LQE: A Fuzzy Link Quality Estimator for Wireless Sensor Networks[END_REF], for example. In general, higher SNR leads to lower probability of error in the packet. Hence, a link with high SNR is considered a high-quality link [START_REF] Farahani | ZigBee Wireless Networks and Transceivers[END_REF]. We use the RSS, SNR, RTT, and TxRate as values to measure the link quality because their values retrieve insight of the performance of a wireless network [START_REF] Flushing | A mobility-assisted protocol for supervised learning of link quality estimates in wireless networks[END_REF]. Therefore, we call RSS, SNR, RTT, and TxRate "link metrics" or "link parameters" in general.

We use the term "broadcast" to refer to the message propagation in a router's neighborhood in order to obtain the link measurements. Also, we refer to the control packets of routing protocols as "hello" messages or beacons and to the packets used in active measurements as probe packets. Finally, we define the term controlled mobility as the ability of some nodes to move by themselves to a specific destination or with a specific goal, i.e., the opposite of randomly [START_REF] Natalizio | Controlled mobility in mobile sensor networks: advantages, issues and challenges[END_REF].

In this paper, we use the DSR [START_REF] Johnson | Ad Hoc Networking[END_REF] protocol for our set of simulations. The DSR protocol is a self-maintaining routing protocol designed for multi-hop wireless networks composed of mobile nodes. DSR uses on demand routing allowing each source to determine the route used to transmit its packets to the corresponding destinations. DSR consists mainly of two mechanisms, Route Discovery and Route Maintenance. Route discovery cycle is used to find a route between the source and the destinations on demand. Route maintenance is used to ensure that the paths remain optimum and loop-free as network conditions change. DSR avoids additional traffic, for example, hello packets by using source routing, i.e., the entire route is part of the packet header and by storing the routes in caches.

IV. ADAPTIVE POSITIONING ALGORITHM

A new quality-of-service-based architecture for substitution networks presented in [START_REF] Razafindralambo | Promoting Quality of Service in Substitution Networks with Controlled Mobility[END_REF] envisions a wireless network composed of mobile routers/relays that provide alternative paths to the base network. Such substitution routers are able to move on demand, so, they can self-deploy and adapt to the network topology accordingly to the environment conditions.

Previously, we have presented the Adaptive POsitioning aLgOrithm [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF] (APOLO) for self-deploying mobile routers in a substitution network. During the substitution network lifetime, APOLO is executed in each mobile router to determine whether it has to move by using the feedback of the link quality coming from one-hop neighbors. APOLO consists of three major stages. Firstly, APOLO measures the link quality by means of one link parameter, e.g., RSSI, SNR, or delay. Secondly, APOLO computes the gathered data and makes the movement decision, i.e., if the router needs to move or not to improve the link quality. And finally, APOLO determines direction of the movement and the router moves accordingly.

Results presented in [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF], [START_REF] Miranda | Adaptive router deployment for multimedia services in mobile pervasive environments[END_REF] are restricted to only one propagation model (2-ray ground) and 3 simulation scenarios. In this paper, we extend these results with extra propagation models and scenarios. First, we present the results obtained when the router's initial position is random. Second, we study the behavior of our algorithm when there exist multiple mobile routers between the source and the destination. Then, we evaluate the redeployment capacity of the mobile router when a new node arrives. Finally, we compare the deployment performance of each link parameter under three different propagation models (2-ray ground, shadowing, and ricean).

V. SIMULATION ENVIRONMENT

We present an extension to the experimental performance evaluation of APOLO. Our main goal is to present the effectiveness of the algorithm to deploy wireless mobile routers in a given area. To that end, we evaluate our proposal by using the NS-2 network simulator2 . In our previous work [START_REF] Miranda | Adaptive router deployment for multimedia services in mobile pervasive environments[END_REF], we have chosen three scenarios proposed in [START_REF] Xie | Multisource, Multidestination, Multirelay Wireless Networks[END_REF] as a result of the study on relay wireless networks. We propose three additional scenarios plus a propagation model comparison.

Since our goal is to assess the impact of controlled mobility in wireless routers, we use the Dynamic Source Routing (DSR) protocol for our simulations, although, APOLO is not tied to any routing particular protocol. Table I summarizes the basic parameters used in our simulations in NS-2. In this paper, we use the instantaneous throughput (TH ins ) defined as he number of bits transferred to the final destination in any given instant to assess the performance of our deployment algorithm.

VI. RESULTS

A. Random initial position

In our previous work, the basic scenario is composed of one mobile router, one source node (S), and a destination node (D). The source and the destination are placed 250 m away from each other, i.e., the source is placed at coordinates (0,0) and the destination at coordinates (250,0). Finally, at the beginning of the simulation, the router node is placed 10 m away from the source node, that is, at coordinates (10,0) as depicted in Fig. 2. Then, the router starts moving based on APOLO. Nevertheless, the mobile router may reach the position that equalizes the parameter values regardless of its initial position.

Hence, we take again this basic scenario. We run a set of simulations choosing the initial position of the router randomly. We use the 802.11b standard along with the tworay ground model. while using the RSS as link metric and Fig. 3(b) presents the results while using the SNR as link metric. In Fig. 3(a) the router's initial coordinates are (23,0), (128,0), and (160,0), respectively. The theoretical position that equalizes should be (125,0) where the router is placed at exactly the middle point between the source and the destination, and therefore, the link values of X prev and X next should be the same. We observe in Fig. 3(a) that the router reaches such a position regardless of its initial position, an expected result since the two-ray ground model calculates the RSS as a function of the distance. Similarly, in Fig. 3(b) the router's initial coordinates are (42,0), (147,0), and (206,0), respectively. Despite the router does not reach a steady position, this behavior corresponds to the previous simulations where the router's initial position is (10,0), in other words, the initial position of the router does not affect the movement behavior by using SNR as link metric. We believe that such a behavior is due to the propagation model we have used. In order to corroborate this, we perform a set of simulations with different propagation models. The results are presented in Section VI-E.

B. Multiple routers scenario

In [START_REF] Miranda | Adaptive router deployment for multimedia services in mobile pervasive environments[END_REF], we study the performance of APOLO by considering a scenario with two routers. In such a scenario, there is a source and a destination communicating though two mobile routers, so, we extend this scenario by considering three and four intermediate routers between the source and the destination as shown in Figure 4.

1) Three routers: Regarding the three router scenario, the source, once again, is placed at coordinates (0,0) and the destination at coordinates (300,0), that is, 300 m away from each other. At the beginning of the simulation, Router 1 is placed at coordinates (10,0), Router 2 is placed at (150,0), and Router 3 is placed at (290,0). Then, the routers execute APOLO to adjust their position using the RSS as link metric, the results are presented in Figure 5. The deployment evolution is plotted as x coordinates as function of simulation time where we observe that the behavior of the routers follows the results obtained with the two router scenario (Figure 5 2) Four routers: Regarding the four router scenario, the source is placed at coordinates (0,0) and the destination at coordinates (400,0), that means, 400 m away from each other. At the beginning of the simulation, Router 1 is placed at coordinates (10,0), Router 2 is placed at (140,0), Router 3 is placed at (260,0), and Router 4 is placed at (390,0). Subsequently, each router adjusts its own position by executing APOLO using RSS as link metric. Figure 6(a) shows the routers deployment through the simulation time. Once again, the final position of the routers equalize the link metric and it is equidistant between nodes. These results, three and four routers, show that the behavior experienced with only one mobile router is duplicated, and therefore, APOLO is a scalable solution and it is able to deal with multiple router scenarios.

C. Two sources and one destination scenario

By the same token, we evaluate APOLO in a multiple destination scenario [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF]. In addition, we present a topology with multiple sources by using the topology depicted in Figure 7, where we illustrate two sources (n0, n1) and one destination (n3) out of range. Thus, a mobile router (n2) is used to connect the sources and the destination. At the beginning of the simulation, the router (n2) is placed 10 m away from the source nodes (n0, n1) on the straight line that connects the sources from the middle position between the receiver node (n3), and finally, we use User Datagram Protocol packets with a size of 1 MB since UDP is used in most multimedia applications.

In this scenario, two identical CBR/UDP flows are transmitted from the source nodes (n0, n1) to destination node (n0) starting and finishing at the same time. A priori, we assume that the best position is located at the coordinates (83,125), which is the triangle centroid. Then, the router uses APOLO to decide where to move and RSS as link metric. The movement trace is depicted in Figure 8(a). During the first 500 s, the router moves in a straight line from [START_REF] Razafindralambo | Promoting Quality of Service in Substitution Networks with Controlled Mobility[END_REF]125) to (94,125), i.e., it travels 84 m. After this time, the router moves from left to right (in the y axis domain) in a range of ±3 m, i.e., from (94,128) to (94,122). This behavior is very different from that one experimented in a similar scenario with two source nodes and one destination. In the latter scenario, the router moves mostly in the x axis range and stops very close to the triangle centroid. Hence, the oscillation experienced in two source scenario is caused by the two flows arriving to the router, that means, the router moves to improve the link quality accordingly to the data flow arriving at the time. In order to avoid wasting energy with short distance movements, it is possible to implement a movement threshold, for example, the router moves if the RSS value drops under certain threshold.

D. Redeployment

One issue that remains open is the routers redeployment. The redeployment is specially important in dynamic scenarios. In the following, we present a simulation campaign where the redeployment is needed. As in the previous set of simulations, the mobile router executes APOLO to redeploy and uses RSS as link metric. At the beginning of the simulation, the scenario is the one depicted in Figure 2, one source node, one destination node, and one mobile router. The source (n0), the router (n1), and the destination (n2) are located at coordinates (0,0), (10,0), and (250,0), respectively. Then, after 650 s a new source node (n3) arrives to transmit data to (n2), and therefore, the router must adapt its position. Node (n3) appears at coordinates (0,125).

Figure 9 plots the movement of the router in the Cartesian space. The first seconds of the simulation, the router follows the same behavior than in the previous simulation, in other words, the router reaches the position at (125,0). Then, when the second source appears, the router starts to move to equalize the quality of the new link between (n3) and (n1). Finally, the router reaches its final position at coordinates (124,60). These results are very interesting for two reasons. Firstly, they prove that APOLO is useful to redeploy automatically mobile routers, and hence, it is well suited in dynamic scenarios. And secondly, the results prove the importance of the hello messages to advertise the eventual changes in the network topology, if the transmission rate of such hello messages is too low, the information gathered may not reflect the changes in the topology over the time. Nevertheless, it is also important to consider the cost of such hello messages in terms of energy and overhead. To overcome this problem, it is interesting to study the optimal transmission frequency of the hello packets [START_REF] Li | Mobility Prediction Based Neighborhood Discovery in Mobile Ad Hoc Networks[END_REF] as well as the overhead reduction techniques.

E. Propagation model comparison

The propagation models are empirical mathematical formulations to characterize the radio wave propagation based on Each propagation model computes the attenuation of the signal strength between the sender and the receiver by using a Carrier Sensing Threshold (CSThresh_). If the signal strength is lower than CSThresh_, the packet is discarded at the physical layer. Otherwise, the signal strength is compared to a second threshold at the receiver (RxThresh_) to determine whether the packet is received with errors or not. If so, the MAC layer discards the packet.

Free space model represents the transmission range as a perfect circle around the sender. Basically, if the receiver is within the circle, it will receive all the packets; otherwise, it loses them. Two-ray ground reflection model considers both the direct path and a ground reflection path, a difference from the free space model, which only considers a single line-of-sight path. The two-ray ground model gives more accurate prediction at a long distance than the free space model. Nevertheless, the free space model is used when the distance is small because the two-ray model does not give a good result for a short distance due to the oscillation caused by the constructive and destructive combination of the two rays. It is important to notice that both models represent the communication range as a prefect circle, i.e., the received power is a deterministic function of distance. On the other hand, the shadowing model takes the fading phenomenon into account. Finally, the Ricean model characterizes the effect of small-scale fading (Rayleigh and Ricean). Such a fading is caused by movement of the sender, receiver, or of other objects in the environment. This movement may be characterized by the Doppler spreading.

As in the previous sections, we evaluate the performance of APOLO under three different propagation models, Ricean, Two ray ground, and Shadowing. To that end, we use the one source-one destination scenario (Figure 2), the router is placed at coordinates (10,0). Then, we vary the propagation model for each of the link parameters, i.e., RSSI, SNR, RTT, and transmission rate. The results obtained are presented in Figure 10. Figure 10(a) presents the comparison of the router deployment by using all the APOLO variants for each model propagation. The Two-ray ground plot was presented in [START_REF] Miranda | Adaptive Deployment Scheme for Mobile Relays in Substitution Networks[END_REF], where router using the RSS variant reaches exactly the middle point between the source and the destination, i.e., at coordinates (125,0) while the router using the SNR and TxRate does not reach a steady point. However, this behavior changes completely when we evaluate APOLO by using the Ricean and Shadowing models. Under both models, Ricean, and Shadowing the performance of the three variants is similar. None of the variants reaches a steady point still the router moves ±10 m away from the middle point (125,0). Nonetheless, this behavior confirms our observation about the SNR performance obtained in Section VI-A, that is, since each propagation model characterizes in different way the events at the physical layer, the values of the link metrics correspond to such characterization and behave accordingly. We also include a comparison of each link parameter under all the propagation models to clarify the difference in the behavior (Figure 10(b)). Because the link quality values depend largely on the propagation model, it is important to choose the one that characterizes better our case of study. In general, the NS-2 community uses the two ray ground model but the shadowing model corresponds better to the real scenarios.

VII. CONCLUSION AND FUTURE WORK

We have presented the impact of controlled mobility to selfdeploy routers in substitution networks. The results provide a wider view of the performance of the Adaptive POsitioning aLgOrithm (APOLO). They prove that APOLO is able to successfully deploy the mobile routers in several scenarios and by using different propagation models. Even more, APOLO performs well also when router redeployment s needed.

We observed that by using the Ricean and Shadowing models the deployment performance of the SNR and TxRate variants outperform the two-ray ground one even if in the former case the router does no reach a steady point. This disadvantage may be overcome by adding a threshold to avoid useless movements. Thus, we are interested in studying how the threshold choice may (or may not) impact the performance.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Basic scenario composed of one mobile router, one source node, and one destination node.

  (a)). The routers travel the corresponding distance to equalize the values of the link metric. In this case, Router 1 and Router 3 travel a similar distance. The routers reach their final position after 550 s, which are, Router 1 at 75 m, Router 2 at 150 m, and Router 3 at 225 m from the source, that means a distance of 75 m between each node. Figure 5(b) plots the instantaneous throughput obtained during the routers deployment.

Fig. 4 .

 4 Fig. 4. Multiple routers scenario composed of three mobile routers, one source node, and one destination node.

Fig. 6 .

 6 Fig. 6. Multiple routers scenario composed of four mobile routers, one source node, and one destination node.

Fig. 7 .

 7 Fig. 7. Two sources, one destination, and one mobile router scenario.

Fig. 8 .

 8 Fig. 8. Scenario two sources and one destination. Movement of the mobile router through the time and the corresponding throughput.

Fig. 9 .

 9 Fig. 9. Redeployment of a mobile router.

Fig. 10 .

 10 Fig. 10. Evaluation of APOLO under different propagation models. The movement of the mobile router as function of time.

TABLE I .

 I SIMULATION PARAMETERS.

	Physical	Propagation	Two Ray Ground
		Error Model	Real [13]
		Antennas Gain	G t = G r = 1
		Antennas Height	h t = h r = 1 m
		Min Received Power	P r-thresh =6.3 nW
		Mobile Router Energy	50 J
		Communication Range	240 m
	MAC	802.11b	Standard Compliant
		Basic Rate	2Mbps
		Auto Rate Fallback	1, 2, 5.5, 11 Mbps
	LLC	Queue size	50 pkts
		Policy	Drop Tail
	Routing	Static	Dijkstra [14]
		Routing Traffic	None
	Transport and	Flow	CBR / UDP
	Application	Packet Size	512 B/1 MB
	Statistics	Number of samples	k = 10
		Broadcast period	t = U(0.1)
	Mobility	Movement step	d = 2m

This work was partially supported by a grant from CPER CIA and the ANR RESCUE project.

http://isi.edu/nsnam/ns/


David Noël
email: david.noel@imag.fr

Marlène Villanova-Oliver
email: 33476827280marlene.villanova-oliver@imag.fr

Pierre Le

Jérôme Gensel
email: jerome.gensel@imag.fr

Modeling semantic trajectories including multiple viewpoints and explanatory factors: application to life trajectories

Keywords: Semantic trajectories, Residential trajectories, Geospatial lifelines, Individual lifeline

In this paper, we propose a semantic trajectory model handling complex trajectories. We consider that a trajectory is composed of multiple aspects which are all different viewpoints from which it can be observed. This model also allows for the representation of explanatory factors that influenced the episodes that compose a trajectory. We here deal with a particular type of trajectory: the life trajectories of individuals or citizens. The residential aspect in life trajectories is particularly relevant for decision makers and urban planning experts who try to understand the residential choices of inhabitants in order to adjust their decisions. Those choices depend on factors related to the home (type, size...), and to the surroundings (accessibility, amenities ...) but they can only be fully apprehended by taking into account the life circumstances of the individuals, along their family, or professional or even spare-time activities viewpoints.

INTRODUCTION

Urban planning experts and decision makers face many challenges related to residential choices of inhabitants of metropolitan areas. These choices are strongly influenced by the various phases individuals go through in their personal lives. Thus, in general, couples with children prefer to live away from the metropolitan centers while those latter, in general, attract a higher proportion of both newly independent and retired people [START_REF] Bonvalet | Family and housing: recent trends in France and Southern Europe[END_REF]. This illustrates some of the most important problems that major cities have to solve. This exodus of working couples with (young) children to peri-urban areas makes it difficult for the cities of the peripheries to provide the necessary amenities (for instance, nurseries and schools), but also increases the time workers need to commute from home to work, which generates pollution and traffic congestion. Similarly, in city centers, one witnesses the emergence of problems of cohabitation between two age categories with sometimes different lifestyles. The diversification of the population of city centers and the periphery of these cities is an important issue and it is essential for decision makers and urban planning experts to acquire a better knowledge of residential dynamics. In particular, in order to make their decision, they try to better understand what is at stake for an individual or a household in the process of choosing a residence.

Reasons for residential choice can be provided from a comprehensive approach to life trajectories of individuals that takes into account many decisive aspects of their lives: familial, professional... The living conditions, especially what is related to the characteristics of the residence and its neighborhood, the lifestyle preference [START_REF] Walker | Latent lifestyle preferences and household location decisions[END_REF], as well as other elements linked to the economic conditions must also be considered [START_REF] Dieleman | Modelling residential mobility; a review of recent trends in research[END_REF]. In this work, we specifically aim to take into account how individuals feel impacted by these elements. Then, in order to study the residential trajectory of an individual (the succession of its residential choices in time and space), it should be considered as an integrated part of a broader vision of her/his life trajectory. This part is one of the multiple and interconnected viewpoints (already demonstrated in computer sciences by Thériault [START_REF] Thériault | A spatio-temporal data model for analysing personal biographies[END_REF]) from which the life trajectory of an individual can be observed.

Our goal is to provide a generic model able to support this complexity related to the multi-dimensional nature of a life trajectory and to explanatory factors that each viewpoint may encompass to explain its evolution or the evolution observed in another viewpoint. For example, in the case of life trajectories, a move (from the residential viewpoint), may be explained by a change from a professional viewpoint (career development, job loss, etc.). Beyond this trivial example, one issue is the representation of the combination of several explanatory factors of various kinds (a change of job may have imposed a move, the beginning of a sense of insecurity may initiated it). Finally, another issue is the opportunity to represent, beyond the observed true facts (e.g. an observed true move), projects that contribute to an ideal of residential trajectory (e.g. a desire to settle down in a particular place, or in a particular type of home, etc.). In this work, we therefore provide a model handling the complexity and variety of trajectories by combining the concept of viewpoint with a time structuration relying on episodes and events. Our model includes also explanatory factors as they may be reported by individuals. This work uses life trajectories as an application case for the modeling and analytics of human mobility in the urban context.

The rest of the paper is organized as follows: we introduce in section 2, the notion of life trajectory. We present in section 3 a brief state of the art on semantic trajectory modeling and life trajectory modeling. Then we propose in section 4 our semantic life trajectory model which integrates multiple viewpoints and explanatory factors. Section 5 describes how this model can be exploited. Finally, we conclude and give directions for future work in section 6.

REPRESENTING AND STUDYING LIFE TRAJECTORIES

Figure 1 (adapted from Thériault [START_REF] Thériault | A spatio-temporal data model for analysing personal biographies[END_REF]) shows a part of the life trajectory of an individual. The life trajectory is represented here as a succession of states which are characterized by values of different statuses or attributes describing this individual. These attributes can be grouped according to the different aspects of the life of a person (such as residential, family, work, hobbies, etc.). These different groups of attributes can therefore be considered as different trajectories targeting a particular theme. Therefore, our representation of life trajectory is multidimensional, each dimension corresponding to a "thematic" focus. Thus, for example, the residential trajectory is represented by statuses is owner, rent/loan, housing type and city (see Figure 1). Any status, and consequently any trajectory is intrinsically temporal, as related to a timeline that ordered its different states. In Thériault's work (see Figure 1), the residential and the professional trajectories are spatiotemporal trajectories since they each contain an attribute describing spatial information: the city of residence, and the city of employment. Such an information could be considered at another spatial scale, such as a neighborhood for the residential trajectory or as x, y coordinates. Other aspects of the life of the individual may also contain a spatial component, and be useful for the study of residential trajectories, for example the location where a hobby is practiced.

As underlined by the French sociologists Yves Grafmeyer and Jean-Yves Authier [START_REF] Grafmeyer | Sociologie urbaine[END_REF], the term "residential trajectory" "tends to suggest that successive positions in a given set is not simply by chance, but rather are linked together by an intelligible order." As a matter of fact a residential trajectory is not just a series of spatiotemporal positions.

Part of our objective is to make it possible to understand the meaning of residential trajectories by bringing to light the underlying reasons why individuals move in a given space, at a specific moment of their lives. The degree of control of an individual on her/his trajectory differs, and it seems to be appropriate to highlight the conditions under which each individual makes her/his own choices. More broadly, we want to elicit the explanatory factors or combinations of factors that have shaped a given trajectory. Thus, somehow what we seek to bring out here is close to the notion of career such as it has been defined by Howard Becker [START_REF] Becker | Outsiders: studies in the sociology of deviance[END_REF]. This concept "refers to the sequence of movements from one position to another" and includes "both objective facts of social structure and changes in the viewpoints, motivations, and desires of the individual". In the case of a residential trajectory, these factors are first to be found in the context surrounding the life trajectory of an individual. There are of course some internal factors which are directly linked to the specific characteristics of one or more viewpoints of this life trajectory. But, there are also some explanatory factors which can be external and so exogenous to the considered life trajectory. Among such external factors are, for instance, the housing market or change in the surroundings of the housing, etc... These external factors have nevertheless to be considered in correlation with the life trajectory. For instance, the fact that housing market prices are rising may have an impact depending on the salary of the individual/household and thus on her/his professional trajectory.

In this work, we are particularly interested in those external factors which may be considered as plausible explanations, whether they are explicitly mentioned by the individuals or not.

Representing life trajectory is complex because it is composed of many descriptive attributes which may refer to different aspects of the individual life. The structuration using viewpoints aims to facilitate the overall comprehension and to offer a better readability of some salient characteristics attached to a particular thematic focus. The representation of a life trajectory is highly dependent on the domain of the study and on its purpose. For a study in urban development, the focus is on the attributes describing the residential trajectory, but explanatory factors can potentially be found in other foci. The study of life trajectories requires the use of suitable referential for considering the various parts of the trajectory separately but also in their interrelationships. Thus, a relevant modeling will enable the integration of explanatory factors of the trajectory, whether internal or external.

RELATED WORK 3.1 Modeling semantic trajectories

Many semantic trajectory models have been proposed in recent years, offering different solutions to enrich space-time trajectories. Most of these semantic trajectory models are based on different kinds of segmentation proposed for spatio-temporal trajectories. Indeed, following Hägerstraand and the "time-geography" [START_REF] Hägerstraand | What about people in regional science?[END_REF], researchers have modelled the spatio-temporal trajectories through periods of trips and periods of activities [START_REF] Zheni | A semantic approach for the modeling of trajectories in space and time[END_REF], or through moves and stops [START_REF] Spaccapietra | A conceptual view on trajectories[END_REF]. These structures are then used to add information about the trajectory, like the transportation mode during a trip, or the nature of an activity. Such information can, for example, be related to the nature of the moving object, the nature of the mode of transportation, or the visited places. These authors propose especially solutions to enrich raw GPS data indicating the path of a moving object, which result in trajectories encompassing useful information in their description (see Figure 2). Depending on the scale level of the trajectory, raw data are not necessarily a series of GPS points. Indeed, in the case of life trajectories and when focusing on the residential aspect (or residential trajectory), the essential spatial component is the location of residence, which can considered at different scales (address, district or, as in our example, the city). This, therefore, implies to consider a sequence of points or areas, indicating the successive residences of a person. When considering the structuration proposed by Spaccapietra [START_REF] Spaccapietra | A conceptual view on trajectories[END_REF], the positions of such places of residence, which persist over time, can be considered as "stops" in the life trajectory of an individual.

In Figure 2, the moving object is a person (individual, citizen) whose travels and moves are examined at the scale of the day. We understand thanks to some semantics (annotations) added to the trajectory that this person went to work on a bike, and after being back home she drove to the supermarket, information that was not contained in the raw trajectory. More broadly, any information which would make sense or help to describe or explain a trajectory more deeply than raw date (usually a series of triplets (latitude, longitude, time)), should be included in a semantic trajectory model [START_REF] Alvares | A model for enriching trajectories with semantic geographical information[END_REF].

Modeling life trajectories

The work conducted by Marius Thériault is a reference in the field of the life trajectory modeling. The space-time model for the analysis of life trajectories [START_REF] Thériault | A spatio-temporal data model for analysing personal biographies[END_REF] is based on three different trajectories -residential, family and professional. Each of these trajectories is conceptually modeled by episodes -stable statutes during a time interval -and events altering one or more of these statutes. The conceptual model is based on a relational approach. Later, the model has been modified in order to determine the likelihood of an event occurring under certain conditions in a life trajectory [START_REF] Thériault | Temporal GIS and statistical modelling of personal lifelines[END_REF]. The conditions of the residential choices are also addressed by [START_REF] Vandersmissen | Modeling propensity to move after job change using event history analysis and temporal GIS[END_REF] with a strong emphasis on the role of job changes occurring in the professional life of individuals. The models proposed in these works are centered on the temporal aspect of residential choices: the focus is more on why people have moved at some place (depending on their life circumstances) than on why they have chosen the place where they have moved to.

The aforementioned approaches have clearly laid the conceptual foundations on which we rely for the representation of life trajectories. Our work, however, aim to enrich this representation by a model of semantic trajectories that handles multiple semantic viewpoints and integrates explanatory factors about trajectories, whether these trajectories belong to a single project of life in the minds of individuals, or are drawn from proved observations.

A SEMANTIC TRAJECTORY MODEL 4.1 Modeling semantic trajectories

In order to address the issue of the different viewpoints from which a trajectory is observed, we rely on the concept of point of view 1 (see [START_REF] Ullman | Principles of Database and Knowledgebase Systems[END_REF]). A viewpoint is a perception among many that an observer has of a studied entity. The point of view consists of a subset of the attributes describing the entity that includes the key attributeor the set of attributes -which form (s) its identifier as well as a subset of some other attributes. The identifier of the entity is always present in a point of view (or seen from this point of view). Any other attribute can be part of several points of view. According to the most common design of point of view (corresponding to the notion of views in DataBase Management Systems), we consider that the entity, whose trajectory is studied, is unique. The union of the points of view forms a complete picture (all attributes are represented) and coherent (all the attributes have the same value in every point of view) of the entity. In our case study, the three viewpoints "residential, "family" and "professional" are essential because they are aspects of life that must absolutely be taken into account to find the explanatory factors behind residential trajectory. Other viewpoints may appear, however depending on the interests of the studied individual, such as leisure activities, which may indeed also influence residential choices. In the following sections, we define the key concepts of our proposal.

The life trajectory structuration

In this work, we combine the approaches of Leibniz and Newton.

While the former considers time as a succession of events, the second considers it as a flow measurable in absolute terms [START_REF] Claramunt | Managing time in GIS an event-oriented approach[END_REF]. Indeed, we consider the evolution of time as a succession of events, but without renouncing to measure it, using available units (year, day, hour ...). Our approach incorporates considerations carried out by Claramunt and Theriault [START_REF] Claramunt | Managing time in GIS an event-oriented approach[END_REF] [8] in their work on time management in geographic information systems.

The first problem is to define the temporal granularity adapted to the modeling of life trajectories. According to [START_REF] Jensen | The consensus glossary of temporal database concepts-february 1998 version[END_REF], a chronon is a minimum amount of time, the smallest time stamp unit for an event. In the case of a life trajectory, a relevant chronon may be the day since this unit allows to locate important events in time with a precision that makes sense for an individual (such as the date of her wedding, the birth of a child, etc.). However, at the scale of life it is useful to use a chronon of other granularity, such as month or year, to locate an event for which accuracy in terms of day is impossible (for instance, when the precise date has been forgotten) or not required (for instance, when day accuracy is useless). The model must therefore supports varying degrees of temporal accuracy. Our life trajectory model is composed of episodes which describe the stable state of a person when observed or considered from a given viewpoint. The state of a point of view is considered stable when the values of all its attributes remain unchanged. This modelling choice requires to choose carefully the information to represent (i.e. the relevant attributes), but also to determine the relevant degrees of precision. For instance, regarding the rent of some accommodation, the precise amount might be less relevant than a range of values. This allows to categorize and discretize information (low rent, high rent, etc.) and it has also the advantage of ensuring a certain stability for the value of the involved attributes. It might be indeed pointless for the overall objective (better understand the residential trajectories) to record a new episode simply because the rent has slightly increased. The model is also composed of events that correspond to things that happen and that can be observed according to [START_REF] Abler | Spatialorganization: the geographer's view of the world[END_REF]. The event usually marks the transition from one stable state to another in one point of view (start and end of episodes).

Definition of an episode. An episode is the stable state of a person seen from a certain point of view during a time interval. The episode duration corresponds to a time interval between two instants ts and te (as ts < te). Each of these two instants may correspond to an event in the trajectory.

Let Epi be an episode of the life trajectory of a person P observed from a point of view i. It is composed of the kP identifier of P and of attributes aj, …, ak, and is valid over a time interval [ts, te]. We note:

P.i.Epi(kP, aj, …, ak) [ts, te]

In the example of Figure 1 showing the life trajectory of a person called Leo, an episode valid from 05/20/2000 to 06/30/2004 is noted as follows:

Leo.residential.Epi (kP = 123, City="Seattle", Housing_type="Apartment", Rent=[400; 600]) [05/20/2000, 06/30/2004]

A non-strict order relation can be established between episodes using algebra of Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

Definition of an event. An event is related to a point of view i for an individual P. It has an identifier kEvt, a name evt_name, and is associated with a chronon t relevant to the observed phenomenon (allowing to locate the event temporally). We note:

P. i.Evt (kEvt, evt_name) t

For example an event move occurred on 06/30/2004 in the trajectory of Leo and is noted in the residential point of view:

Leo.residential.Evt (KEvt = 1, evt_name = "move") 06/30/2004

The evt_name attribute is selected from a controlled vocabulary and describes the nature of the event. An ontology structuring all of the vocabulary specific to each point of view is being defined.

Definition of a trajectory. The life trajectory T of a person P consists of the union of the points of view i, each being defined by a set of events and episodes. We note:

P.T = {U P.i} for i ∈ {Residential, Professional, Family, ...} A simplified trajectory observed from a single point of view i composed of two events and two episodes with the one still ongoing can thus be noted as follows:

P.T.i =

Integrating explanatory factors

Considering that the life trajectory of a person includes events which modify its state under a given viewpoint, it is essential to model the explanatory factors which can be associated with these events.

The explanatory factors can be internal or external, which means that they can either be related to life circumstances of the individual or dependent on factors that are not directly related to these circumstances. For example, internal factors may be related to the birth of a child or to professional situation changes. It therefore appears that in our model, the events themselves may be explanatory factors. Thus, the event "job change" may be an explanatory factor behind the "move event. The explanatory factors of the residential trajectory of the individual can also be found in environmental conditions (economic, social, etc.) within which the individual evolves. This is for example the case of the price of the real estate market that may limit acquisition or rental into a given neighborhood. However, we only want to model these external factors if they have some impact on individuals, and specifically if these factors are explicitly mentioned by them. In this case, an event related to a feeling expressed by the individual is added to the trajectory. Thus, the event "Feeling of insecurity" is an example2 .

An explanatory factor F is associated with the event it explains. Each event can be explained by several factors. The above definition for an event is extended and we note:

P.i.Evt(kEvt,, evt_name, {F1,…, Fn)t with Fj (kExp, description)

Each explanatory factor Fj combines the identifier kExp of an event (the explanation) and a description attribute used to specify the influence of the event for the view i to which belongs the explained event kExp.

EXPLOITATION OF THE MODEL

In this section, we present how the proposed model can be exploited. First we show how the concepts defined so far (episodes, events and explanatory factors) can be used in order to enrich the representation of life trajectories by modeling the expectations of an individual. Then, we illustrate with a few examples the possibilities of knowledge exploitation allowing by the model.

Observed trajectory and expectations

The explanatory factors of residential choices, whether they are linked to known facts or to feelings of the individual are not always sufficient to explain its trajectory. Individual projects, or more broadly, their desires or aspirations must be considered and therefore modeled. The concepts presented above (episodes, events and explanatory factors) can be exploited for this purpose. We can represent either the observed trajectory of individuals or the plans they have made or are making for the future. Thus, it is possible to represent residential or professional projects that Leo has made in the past while he was living in Portland, and the reasons for these choices (the events and the explanatory factors are shown in Figure 5): Leo.residential_project.Epi (kP=35, City="Redmond", Housing="Apartment") [2000,2005] Leo.professionnal_project.Epi (kP=35, City_of_employment="Seattle", Occupational_status="Student") [2000,2005] Leo.residential_project.Evt(KEvt=E1, evt_name="Offer") april2000

Leo.professional_project.Evt(KEvt=E2, evt_name="JoinSchool", F1) april2000

Leo.projet_résidentiel.Evt(KEvt=E3, evt_name="Move", F2) august2000 F1 (e1, "My aunt had an apartment in Redmond and she proposed me to live in it. The choice of school in Seattle was thus a viable option") F2 (e1, "The apartment in Redmond was available from August")

This would mean that Leo had planned in April 2000 to join a school in Seattle (event E2) because he could live in the apartment of his aunt for free (event E1) (and not the reverse, he has not considered moving in Redmond because he was joining this school). The move (event E3) was possible in August 2000.

However, although Leo has joined the School of Seattle (event E5) at the beginning of September 2000, it turned out that his aunt had sold her apartment in June 2000, leaving him with no housing solution (event E6). He had therefore to find an alternative accommodation (event E4) near the city of Seattle.

Leo.residential.Epi (kP=35, City="Renton", Housing_type="Studio Apartment") [2000,2001] Leo.professional.Epi (kP=35, City_of_employment="Seattle", Occupational_status="Student") [2000,2005] Leo.residential.Evt(KEvt=E4, evt_name="Move", F4, F5) sept2000

Léo.professional.Evt(KEvt=E5, evt_name="Join School", F1) sept2000

Léo.residential.Evt(KEvt=E6, evt_name="No housing solution") juin2000 F4 (E5, "I joined the school in Portland")

F5 (E6, "My aunt sold her apartment.")

This example illustrates that it is possible to use the model to represent two types of trajectories, the observed (i.e. where and when individuals have actually lived), and one that could have existed or to which the individual aspires. Both can be compared to measure and analyze differences. In particular, interesting cases can occur, such as the one related to e1 event, expressed originally in a planned trajectory but which finally impacts the observed trajectory.

Model querying

The model can be operated with temporal spatial and / or thematic inputs through the use of a query language suitable for the formalism of implementation of the model. Concerning the time dimension, it can for example be used to get the status of one or more individuals at a time t or during a time interval [t1, t2]. For example, we could get the residential situation of Leo (given on figure 1 by the attributes city, housing type, is owner and rent/loan) between two dates. Spatially, it is possible to know which locations (according to the granularity chosen for the spatial attributes of the model) are part of the trajectory of individuals. Such requests may involve the location of residences or places of work and their possible neighborhood. Naturally, applications are also possible on spatio-temporal or thematic aspects.

The model allows also to learn about the underlying factors related to residential mobility for a particular individual or group of individuals. It is for instance possible to focus on a specific event in the trajectory and to look for its causes.

Similarly, queries combining temporal or spatial dimensions with explanatory factors are possible. For the residential point of view, it is possible to know for a given move at what date the first explanatory factor emerged. It is thus possible to define a latency period, which corresponds to a time interval during which an individual is likely planning to move.

CONCLUSION

We have proposed an original model for semantic trajectories integrating multiple viewpoints and explanatory factors. We have demonstrated the utility of these two concepts in order to model life trajectories. The use of the concept of viewpoint allows high adaptability depending on studied informations, besides a classification both in time and between individuals. In addition, the integration model of explanatory factors allows us to better understand the reasons why and circumstances in which people are moving, whether they depend on external or on internal factors to their trajectories.

The implementation of our proposal is in progress and relies on the principles of the TROPES model [START_REF] Mariño | Multiple Viewpoints and Classification Mechanism in Object-Oriented Representation[END_REF]. This approach is particularly interesting because it includes a classification mechanism of instances within each viewpoint.

A data collection will be first performed through a survey led with a representative panel of about fifty people in order to assess the model itself. In a second step, data will be provided by the individuals themselves through an ad hoc online application, before we try to harvest (part of) trajectory data from social networks.

We also work on an algebra and algorithms dedicated to the model exploitation. Besides querying the model, inference techniques will be propose to build some knowledge about trajectories We particularly focus on the possibility of identifying key explanatory factors underlying the reasons of changes observed in a given trajectory, specially residential one.

Figure 1 :

 1 Figure 1: A part of a life trajectory (Adapted from Thériault [18])

Figure 2 :

 2 Figure 2 : From raw data to semantic trajectory (From Yan and Spaccapietra [21])

Figure 3 :Figure 3

 33 Figure 3 : Illustration of the notion of point of view

Figure 4 :

 4 Figure 4 : The explanatory factors of an event. The values correspond to events identifiers.

Figure 5 :

 5 Figure 5 : Observed trajectory and expectations (representation of events and explanatory factors).

Viewpoint and point of view are considered as synonyms in this work.

In accordance with the definitions given above, this creates a new episode due to the change in value of an attribute dedicated to the feeling of insecurity.Note that the explanatory factors can be inter-point of view or intra-point of view: they may depend on events occurring within the same point of view that the event they explain, or on events occurring in another point of view (see Figure4).

ACKNOWLEDGMENTS

We would like to thank the Rhône-Alpes Region Council for his support to our work.


Bernard Carré

A model for calculation of growth and feed intake in broiler chickens on the basis of feed composition and genetic features of broilers

Keywords: poultry, chicken, avian, growth, energy, ME, protein, fat, model, feed intake 2015

. An equation (D) describing protein deposition as a function of protein intake is added to this previous system, in order to obtain a complete description of growth and feed intake depending on feed composition and genetic features of broilers. A calculation is conducted for lean and fat lines with various dietary protein contents. Lean and fat lines are distinguished through the equation expressing lipid deposition as a function of [protein/energy] ratio and protein efficiency, and through the equation (D). The model provides results that are typical of differences between lean and fat lines, with a higher dietary protein recommendation for lean than for fat line, lower feed conversion ratios (FCR) in lean than in fat line, and higher protein efficiencies in lean than in fat line.

Introduction

It was previously shown that the feed intake of broilers could be calculated from the knowledge of feed composition (metabolizable energy (ME) and crude protein (CP) contents) and body weights (BW) at beginning and end of a growth period [START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF]. Thus, BW and growth data were required to calculate feed intake. It is proposed in the current publication to improve this approach by introducing an equation allowing growth to be calculated.

Materials and methods

Calculations

Equations are the 6 equations E1 to E6 shown in a previous publication [START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF], with Equation E2 being replaced by Equation R5 [START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF]. To this system is added the following equation "(D)" describing the daily protein deposition as a function of protein intake with an asymptote "a" and an ascending line "L" having a slope value "P" and an intercept value "E" (Figure 1): (D): Y = a -b e (-c e dX ) With: Y = daily protein deposition (g) X = daily protein intake (g)

The slope P is assumed to depend on the amino acid composition of dietary protein and on the genetic feature of broilers. It is also assumed that P is higher in a lean line than in a fat line as expected from a previous study [START_REF] Leclercq | Further investigations on protein requirement of genetically lean and fat chickens[END_REF]. E represents the endogenous protein losses with the energy requirement being met.

Table 1. Equations of the nutrition model for broilers. Examples of calculations are shown in Table 2. 0.7 = initial body weight (kg) (this value is taken as an example) 28 = mean age (days) of broilers (this value is taken as an example) 14 = duration (days) of growth (this value is taken as an example) 13.01 = Apparent metabolizable energy value of diets, corrected to zero nitrogen retention (AMEn; MJ/kg) (this value is taken as an example) 20.00 = crude protein content (%) of diet (this value is taken as an example) A = final body weight (kg) = 0.7 + B / 1000 × 14 B = daily weight gain (g) = I / H C = (0.7 0.634 + A 0.634 ) / 2 D = (0.7 0.418 + A 0.418 ) / 2 E = daily feed intake (DFI; g) (proposed value) F = fat content of body weight gain (FCG; g/g) (proposed value) G = daily protein deposition (DPD; g) (proposed value) H = protein content of body weight gain (PCG; g/g) = (0.179 + 0.00169 × 28) (1-F) I = DPD (calculated value) for lean line = 13 -11.51e (-0.100 e (0.145 J) ) I = DPD (calculated value) for fat line = 13 -11.51e (-0.100 e (0.131 J) ) J = daily protein intake (DPI; g) = E × 20.00 / 100 K = apparent metabolizable energy value of diet (AME; MJ/kg) = 13.01 + 1000 (0.0344 B × H / 6.25 / E) L = daily intake of AME (MEI; MJ) = 0.68 C + 0.03918 × 1.116 B × F + 0.02369 × 1.388 B × H M = protein efficiency (PE; g/g) = I / J N = daily feed intake (DFI) (calculated value) = 1000 L / K O = fat content of body weight gain (FCG) (calculated value) for lean line = 12.99 (0.137 D + 0.025) e (-1.082 × 20.00 / 13.01 -2.09 M) O = fat content of body weight gain (FCG) (calculated value) for fat line = 15.20 (0.137 D + 0.025) e (-1.082 × 20.00 / 13.01 -2.09 M) P = feed conversion ratio (FCR; g For the calculations shown in the current study, a common asymptotic "a" value of 13g/day was attributed to each line. P values of 0.59 and 0.53 were attributed to lean and fate lines, respectively and a constant E value of 0.6 g/day was attributed to each line and each dietary protein concentration, which resulted in the fitted equations shown for "I" in Table 1. Fitting of these equations were obtained by fixing the Y and X values at Y = 0.95a; 0.75a; 0.62a; 0.50a, as shown in Figure 1.

/g) = N / B Q = (1 -E / N) 2 R = (1 -F / O) 2 S = (1 -G / I) 2
For the equations expressing the lipid content of weight gain shown for "O" in Table 1, the α values [START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF] of 12.99 and 15.20 were attributed to lean and fat lines, respectively, in agreement with the α values found for males from experimental lean and fat lines [START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF].

Results of calculations are shown in Table 2 for lean and fat lines, with dietary protein contents varying from 14 to 26%. Figure 2 is an illustration of Table 2.

Results and discussion

Results of calculations are illustrated in Figure 2. According to the growth curves shown by the model, the lean line requires a higher dietary protein content than the fat line for expressing the growth potential (Figure 2). The model calculation provides feed conversion ratios (FCR) that are lower in lean than in fat line (Figure 2). According to the model, protein efficiencies (PE) are higher in lean than in fat line (Figure 2). All these results are in agreement with experimental studies comparing lean and fat lines [START_REF] Leclercq | Further investigations on protein requirement of genetically lean and fat chickens[END_REF][START_REF] Carré | Cross relationships between growth performance, growth composition and feed composition in broiler chickens, calculated from published data[END_REF], which shows the reliability of the model. Distinguishing lean and fat lines is performed in the model through two equations using a specific 1 for lean and fat lines coefficient for each line. One of these equations concerns fat deposition ("O" in Table 1) with a higher fat deposition in the fat line; the other equation concerns protein deposition ("I" in Table 1) with a better protein efficiency in the lean line. When one of these equations does not express any difference between lines using the same coefficients for both lines, the model fails in expressing all the typical differences between the lean and fat lines. Thus, both equations are needed to express all the differences between lean and fat lines. Considering the process of fat deposition, the equation of fat deposition ("O" in Table 1) expresses the "pull" phenomenon, while the equation of protein deposition ("I" in Table 1) expresses the "push" phenomenon. Thus, it is probably logical that the model works only if the whole process is expressed (the "push" and "pull"). It is stated above that the slope "P" depends on the genetic feature of broilers and on the amino acid composition of dietary proteins. Knowledge about the relationship between "P" and this amino acid composition represents future developments of this model for computing dietary amino acid recommendations.

Figure 1 :

 1 Figure 1: curve describing the protein deposition (Y) as a function of protein intake (X). For a = 13, P = 0.53, E = 0.6: Y = 13 -11.51 e (-0.100 e 0.131X )

Figure 2 :

 2 Figure 2: curves obtained from the model shown in Table1for lean and fat lines

Table 2 .

 2 Examples of calculations of broiler growth performance from the feed composition (energy value and crude protein) and the protein and lipid deposition curve responses assumed from broiler genetics (maximum growth potential and fatness) and amino acid composition of dietary proteins (details of equations are shown in Table1).

	Calculated values
	Proposed values
	Calculated values

Values of E, F and G are found in order to obtain zero for Q, R and S, using the Excel solver system.

Initial BW is 0.7 kg. Mean age of broilers for growth period is 28 days. Duration of growth period is 14 days. AMEn value of diets is 13.01 MJ/kg. "L-14" and "F-14" mean broilers from lean and fat lines, respectively, fed a diet containing 14% crude protein (N×6.25).


Jean-Daniel Boissonnat
email: jean-daniel.boisonnat@inria.fr

Ramsay Dyer
email: r.h.dyer@rug.nl

Arijit Ghosh

A probabilistic approach to reducing algebraic complexity of Delaunay triangulations

We propose algorithms to compute the Delaunay triangulation of a point set L using only (squared) distance comparisons (i.e., predicates of degree 2). Our approach is based on the witness complex, a weak form of the Delaunay complex introduced by Carlsson and de Silva. We give conditions that ensure that the witness complex and the Delaunay triangulation coincide and we introduce a new perturbation scheme to compute a perturbed set L close to L such that the Delaunay triangulation and the witness complex coincide. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lovász local lemma.

Introduction

The witness complex was introduced by Carlsson and de Silva [START_REF] De Silva | Topological estimation using witness complexes[END_REF] as a weak form of the Delaunay complex that is suitable for finite metric spaces and is computed using only distance comparisons. The witness complex Wit(L, W ) is defined from two sets L and W in some metric space X: a finite set of points L on which the complex is built, and a set W of witnesses that serves as an approximation of X. A fundamental result of de Silva [START_REF] De Silva | A weak characterisation of the Delaunay triangulation[END_REF] states that Wit(L, W ) = Del(L) if W is the entire Euclidean space X = R d , and the result extends to spherical, hyperbolic and tree-like geometries. The result has also been extended to the case where W = X is a smoothly embedded curve or surface of R d [START_REF] Attali | Weak witnesses for Delaunay triangulations of submanifolds[END_REF]. However, when the set W of witnesses is finite, the Delaunay triangulation and the witness complexes are different and it has been an open question to understand when the two structures are identical. In this paper, we answer this question and present an algorithm to compute a Delaunay triangulation using the witness complex.

We first give conditions on L that ensure that the witness complex and the Delaunay triangulation coincide when W ⊂ R d is a finite set (Section 3). Some of these conditions are purely combinatorial and easy to check. In a second part (Section 4), we show that those conditions can be satisfied by slightly perturbing the input set L. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the general Lovász local lemma. Its analysis uses the notion of protection of a Delaunay triangulation that we have previously introduced to study the stability of Delaunay triangulations [START_REF] Boissonnat | The Stability of Delaunay Triangulations[END_REF].

Our algorithm has several interesting properties and we believe that it is a good candidate for implementation in higher dimensions. [START_REF] Alon | The Probabilistic Method[END_REF]. Low algebraic degree. The only numerical operations used by the algorithm are (squared) distance comparisons (i.e., predicates of degree 2). In particular, we do not use orientation or in-sphere predicates, whose degree depends on the dimension d and are difficult to implement robustly in higher dimensions. 2. Efficiency. Our algorithm constructs the witness complex Wit(L , W ) = Del(L ) of the perturbed set L in time sublinear in |W |. See Section 5. 3. Simplex quality. Differently from all papers on this and related topics, we do not compute the volume or any measure of simplex quality. Nevertheless, through protection, a lower bound on the thickness of the output simplices can be guaranteed (see Theorem 3), and the resulting Delaunay triangulation is stable with respect to small metric or point perturbations [START_REF] Boissonnat | The Stability of Delaunay Triangulations[END_REF]. 4. No need for coordinates. We can construct Delaunay triangulations of points that come from some Euclidean space but whose actual positions are unknown. We simply need to know the interpoint distances. 5. A thorough analysis. Almost all papers in Computational Geometry rely on oracles to evaluate predicates exactly and assume that the complexity of those oracles is O(1). Our (probabilistic) analysis is more precise. We only use predicates of degree 2 (i.e. double precision) and the analysis fully covers the case of non generic data.

Previous work. Millman and Snoeyink [START_REF] Millman | Computing Planar Voronoi Diagrams in Double Precision: A Further Example of Degree-driven Algorithm Design[END_REF] developed a degree-2 Voronoi diagram on a U × U grid in the plane. The diagram of n points can be computed using only double precision by a randomized incremental construction in O(n log n log U ) expected time and O(n) expected space. The diagram also answers nearest neighbor queries, but it doesn't use sufficient precision to determine a Delaunay triangulation.

Our paper borrows ideas from the controlled perturbation paradigm [START_REF] Halperin | Controlled perturbation for certified geometric computing with fixedprecision arithmetic[END_REF]. The purpose is to actually perturb the input, thereby reducing the required precision of the underlying arithmetic and avoiding explicit treatment of degenerate cases. A specific scheme for Delaunay triangulations in arbitrary dimensions has been proposed by Funke et al. [START_REF] Funke | Controlled perturbation for Delaunay triangulations[END_REF]. Their algorithm relies on a careful analysis of the usual predicates of degree d + 2 and is much more demanding than ours.

Notation. In order to avoid boundary complications, we work on the flat torus

T d = R d /Z d .
Boundary issues are discussed in the full version [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF] of the paper. The landmarks form a finite set L ⊂ T d , but the set of witnesses W ⊆ T d is only required to be closed in T d . If for any x ∈ T d there is a w ∈ W with w -x < ε, we say that W ⊂ T d is an ε-sample. For any finite set L ⊂ T d there is a λ > 0 such that L is a λ-sample for T d for all λ ≥ λ. The parameter λ is called the sampling radius of L. Also, there is a μ > 0 such that p -q ≥ μλ for all p, q ∈ L. We call μ the sparsity ratio of L, and we say that L is (λ, μ)-net. Observe that μ < 2. Indeed, if p and q belong to a (λ, μ)-net L, and q is the closest point to p in L, then μλ ≤ p -q < 2λ.

In order to avoid topological complications associated with the periodic boundary conditions, we impose the constraint λ ≤ 1/4. A simplex σ ⊂ L is a finite set. We always assume that L contains a non-degenerate d-simplex (i.e., L is not contained in a lower dimensional flat).

Delaunay and witness complexes

Definition 1 (Delaunay center and Delaunay complex). A Delaunay center for a simplex σ ⊂ L is a point x ∈ T d that satisfies p -x ≤ q -x , ∀p ∈ σ and ∀q ∈ L. The Delaunay complex Del(L) of L is the complex consisting of all simplexes σ ⊂ L that have a Delaunay center.

Note that x is at equal distance from all the vertices of σ. A Delaunay simplex is top dimensional if is not the proper face of any Delaunay simplex. The affine hull of a top dimensional simplex has dimension d. If σ is top dimensional, the Delaunay center is the circumcenter of σ which we denote c σ . We write R σ for the circumradius of σ.

Delaunay [START_REF] Delaunay | Sur la sphère vide[END_REF] showed that if the point set L is generic, i.e., if no empty sphere contains d + 2 points on its boundary, then Del(L) is a triangulation of T d (see the discussion in Section 3), and any perturbation L of a finite set L is generic with probability 1. We refer to this as Delaunay's theorem.

We introduce now the witness complex that can be considered as a weak variant of the Delaunay complex.

Definition 2 (Witness and witness complex). Let σ be a simplex with vertices in L ⊂ T d , and let w be a point of W ⊆ T d . We say that w is a witness of σ if w -p ≤ w -q , ∀p ∈ σ and ∀q ∈ L \ σ. The witness complex Wit(L, W ) is the complex consisting of all simplexes σ such that for any simplex τ ⊆ σ, τ has a witness in W .

Observe that the only predicates involved in the construction of Wit(L, W ) are (squared) distance comparisons, i.e. polynomials of degree 2 in the coordinates of the points. This is to be compared with the predicate that decides whether a point lies inside, on or outside the sphere circumscribing a d-simplex which is a polynomial of degree d + 2.

Identity of witness and Delaunay complexes

In this section, we make the connection between Delaunay and witness complexes more precise. We start with de Silva's result [START_REF] De Silva | A weak characterisation of the Delaunay triangulation[END_REF]:

Theorem 1. Wit(L, W ) ⊆ Del(L), and if W = T d then Wit(L, W ) = Del(L).
If L is generic, we know that Del(L) is embedded in T d by Delaunay's theorem. It therefore follows from Theorem 1 that the same is true for Wit(L, W ). In particular, the dimension of Wit(L, W ) is at most d.

Identity from protection. When W is not the entire space T d but a finite set of points, the equality between Del(L) and Wit(L, W ) no longer holds. However, by requiring that the d-simplices of Del(L) be δ-protected, a property introduced in [START_REF] Boissonnat | The Stability of Delaunay Triangulations[END_REF], we are able to recover the inclusion Del(L) ⊆ Wit(L, W ), and establish the equality between the Delaunay complex and the witness complex with a discrete set of witnesses.

Definition 3 (δ-protection). We say that a simplex σ ⊂ L is δ-protected at x ∈ T d if x -q > x -p + δ, ∀p ∈ σ and ∀q ∈ L \ σ.
We say that Del(L) is δ-protected when each Delaunay d-simplex of Del(L) has a δ-protected Delaunay center. In this sense, δ-protection is in fact a property of the point set and we also say that L is δ-protected. If Del(L) is δ-protected for some unspecified δ > 0, we say that L is protected (equivalently L is generic). We always assume δ < λ since it is impossible to have a larger δ if L is a λ-sample. The following lemma is proved in [START_REF] Boissonnat | Only distances are required to reconstruct submanifolds[END_REF]. For simplicity, we use star 2 (p ) to denote star(star(p; Del(L)); Del(L)), where star(p; K) denotes the star of p in K, i.e. the smallest subcomplex of K containing the simplices that have p as a vertex. The link of p, link(p; K), is the simplicial complex defined by the simplices in star(p) that do not contain p.

Lemma 1 (Inheritance of protection). Let L be a (λ, μ)-net and suppose p ∈ L. If every d-simplex in star 2 (p) is δ-protected, then all simplices in star(p; Del(L)) are at least δ -protected where δ = μδ 4d . The following lemma is an easy consequence of the previous one (see [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF] for a proof).

Lemma 2 (Identity from protection). Let L be a (λ, μ)-net with p ∈ L. If all the d-simplices in star 2 (p) are δ-protected and W is an ε-sample for T d with δ ≥ 8dε μ , then star(p; Wit(L, W )) = star(p; Del(L)). We end this subsection with a result proved in [3, Lemma 3.13] that will be useful in Section 5. For any vertex p of a simplex σ, the face oppposite p is the face determined by the other vertices of σ, and is denoted by σ p . The altitude of p in σ is the distance D(p, σ) = d(p, aff(σ p )) from p to the affine hull of σ p . The altitude D(σ) of σ is the minimum over all vertices p of σ of D(p, σ). A poorly-shaped simplex can be characterized by the existence of a relatively small altitude. The thickness of a j-simplex σ is the dimensionless quantity Θ(σ) that evaluates to 1 if j = 0 and to D(σ) j∆(σ) otherwise, where ∆(σ) denotes the diameter of σ, i.e. the length of its longest edge.

Lemma 3 (Thickness from protection). Suppose σ ∈ Del(L) is a d-simplex with circumradius less than λ and shortest edge length greater than or equal to μλ. If every (d -1)-face of σ is also a face of a δ-protected d-simplex different from σ, then the thickness of σ satisfies Θ(σ) ≥ δ (μ+ δ) 8d . In particular, suppose p ∈ L, where L is a (λ, μ)-net, and every d-simplex in

star 2 (p) is δ-protected, then every d-simplex in star(p) is δ μ 8d -thick.
A combinatorial criterion for identity. The previous result will be useful in our analysis but does not help to compute Del(L) from Wit(L, W ) since the δ-protection assumption requires knowledge of Del(L). A more useful result in this context will be given in Lemma 5. Before stating the lemma, we need to introduce some terminology and, in particular, the notion of good links.

A complex K is a k-pseudo-manifold if it is a pure k-complex and every (k -1)-simplex is the face of exactly two k-simplices.

Definition 4 (Good links). Let K be a complex with vertex set L ⊂ T d . We say p ∈ L has a good link if link(p; K) is a (d -1)-pseudo-manifold. If every p ∈ L has a good link, we say K has good links.

For our purposes, a simplicial complex K is a triangulation of T d if it is a dmanifold embedded in T d . We observe that a triangulation has good links.

Lemma 4 (Pseudomanifold criterion). If K is a triangulation of T d and J ⊆ K has the same vertex set, then J = K if and only if J has good links.

A proof is given in [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF]. We can now state the lemma that is at the heart of our algorithm. It follows from Theorem 1, Lemma 4, and Delaunay's theorem: Lemma 5 (Identity from good links). If L is generic and the vertices of Wit(L, W ) have good links, then Wit(L, W ) = Del(L).

Turning witness complexes into Delaunay complexes

Let, as before, L be a finite set of landmarks and W a finite set of witnesses. In this section, we intend to use Lemma 5 to construct Del(L ), where L is close to L, using only comparisons of (squared) distances. The idea is to first construct the witness complex Wit(L, W ) which is a subcomplex of Del(L) (Theorem 1) that can be computed using only distance comparisons. We then check whether Wit(L, W ) = Del(L) using the pseudomanifold criterion (Lemma 4). While there is a vertex p of Wit(L, W ) that has a bad link (i.e. a link that is not a pseudomanifold), we perturb p and the set of vertices I(p ), to be exactly defined in Section 4.2, that are responsible for the bad link L(p ) = link(p , Wit(L , W ), and recompute the witness complex for the perturbed points. We write L for the set of perturbed points at some stage of the algorithm. Each point p is randomly and independently taken from the so-called picking ball B(p, ρ). Upon termination, we have Wit(L , W ) = Del(L ). The parameter ρ, the radius of the picking balls, must satisfy Eq. ( 2) to be presented later. The steps are described in more detail in [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF]Algo. 1]. The analysis of the algorithm relies on the Moser-Tardos constructive proof of Lovász local lemma.

Lovász local lemma

The celebrated Lovász local lemma is a powerful tool to prove the existence of combinatorial objects [START_REF] Alon | The Probabilistic Method[END_REF]. Let A be a finite collection of "bad" events in some probability space. The lemma shows that the probability that none of these events occur is positive provided that the individual events occur with a bounded probability and there is limited dependence among them.

Lemma 6 (Lovász local lemma). Let A = {A 1 , . . . , A N } be a finite set of events in some probability space. Suppose that each event A i is independent of all but at most Γ of the other events A j , and that Pr

[A i ] ≤ for all 1 ≤ i ≤ N . If ≤ 1 e(Γ +1
) (e is the base of the natural logarithm), then Pr

N i=1 ¬A i > 0.
Assume that the events depend on a finite set of mutually independent variables in a probability space. Moser and Tardos [START_REF] Moser | A constructive proof of the generalized Lovász Local Lemma[END_REF] gave a constructive proof of Lovász lemma leading to a simple and natural algorithm that checks whether some event A ∈ A is violated and randomly picks new values for the random variables on which A depends. We call this a resampling of the event A. Moser and Tardos proved that this simple algorithm quickly terminates, providing an assignment of the random variables that avoids all of the events in A. The expected total number of resampling steps is at most N/Γ .

Correctness of the algorithm

We write ρ = ρλ and µ = μλ, and we assume ρ < μ/4. The triangle inequality yields a bound on the sampling radius λ and the sparsity ratio μ of any perturbed point set L : λ = λ(1 + ρ) < 2λ and μ = μ-2 ρ 1+ ρ ≥ μ 3 . We refer to the terminology of the Lovász local lemma. Our variables are the points of L which are randomly and independently taken from the picking balls B(p, ρ), p ∈ L.

The events are associated to points of L , the vertices of Wit(L , W ). We say that an event happens at p ∈ L when the link L(p ) of p in Wit(L , W ) is not good, i.e., is not a pseudomanifold. We know from Lemma 2 that if p is a vertex of Wit(L , W ) and L(p ) is not good, then there must exist a d-simplex in star 2 (p ) that is not δ-protected for δ = 8dε/μ . We will denote by -I 1 (p ) : the set of points of L that can be in star 2 The probability 1 (p ) that L(p ) is not good is at most the probability 2 (p ) that one of the simplices of S(p ), say σ , has its δ-protecting zone Z δ (σ ) violated by some point of L . Write 3 (q , σ ) for the probability that q belongs to the δ-protection zone of the d-simplex σ . We have

1 (p ) ≤ 2 (p ) ≤ q ∈I2(p ) σ ∈S(p ) 3 (q , σ ) (1)
The following lemma, proved in [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF] upper bounds |I(p )|, |S(p )|, Γ and 3 (q , σ ).

Observe that the events p and q are independent if I(p ) ∩ I(q ) = ∅. Using Eq. ( 1) and Lemma 7, we conclude that 1 (p ) ≤ 2π d-1 I K δ ρ . An event depends on at most Γ other events. Hence, to apply the Lovász Local Lemma 6, it remains to ensure that 1 (p ) ≤ 1/(e(Γ + 1)). In addition, we also need that δ ≥ 8dε/μ to be able to apply Lemma 2. We thefore need to satisfy 8dε μ ≤ δ ≤ Jρ where J -1 def = 2eπ d-1 IK(Γ + 1). Observe that I, K, Γ and J depend only on μ and d. We conclude that the conditions of the Lovász local lemma hold if the parameter ρ satisfies

µ 4 ≥ ρ ≥ 24dε μJ where J -1 def = 2eπ d-1 IK(Γ + 1) = 2 μ O(d 2 ) (2)
Hence, if ε is sufficiently small, we can fix ρ so that Eq. ( 2) holds. The algorithm is then guaranteed to terminate. By Lemma 5, the output is Del(L ).

It follows from Moser-Tardos theorem that the expected number of times a bad link is encountered is O |L| We sum up the results of this section in Theorem 2. Under Eq. ( 2), the algorithm terminates and outputs the Delaunay triangulation of some set L whose distance to L is at most ρ. The number of point perturbations performed by the algorithm is O I |L| Γ .

Sublinear algorithm

When the set L is generic, K = Wit(L , W ) is embedded in T d and is therefore ddimensional. It is well known that the d-skeleton of Wit(L , W ) can be computed in time O((|W |+|K|) log |L |) using only distance comparisons [START_REF] Boissonnat | The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes[END_REF]. Although easy and general, this construction is not efficient when W is large.

In this section, we show how to implement an algorithm called Algorithm 2 with execution time sublinear in |W |. We will assume that the points of W are located at the centers of the cells of a grid, which is no real loss of generality. The idea is to restrict our attention to a subset of W , namely the set of fullleaf-points introduced in Section 5.2. These are points that may be close to the circumcenter of some d-simplex. A crucial observation is that if a d-simplex has a bounded thickness, then we can efficiently compute a bound on the number of its full-leaf-points. This observation will also allow us to guarantee some protection (and therefore thickness) on the output simplices, as stated in Theorem 3 below.

The approach is based on the relaxed Delaunay complex, which is related to the witness complex, and was also introduced by de Silva [START_REF] De Silva | A weak characterisation of the Delaunay triangulation[END_REF]. We first introduce this, and the structural observations on which the algorithm is based.

The relaxed Delaunay complex

The basic idea used to get an algorithm sublinear in |W | is to choose witnesses for d-simplices that are close to being circumcenters for these simplices. With this approach, we can in fact avoid looking for witnesses of the lower dimensional simplices. The complex that we will be computing is a subcomplex of a relaxed Delaunay complex: Definition 5 (Relaxed Delaunay complex). Let σ ⊂ L be a simplex. An α-center of σ is any point x ∈ T d such that x -p ≤ x -q + α ∀p, q ∈ σ. We say that x is an α-Delaunay center of σ if x -p ≤ x -q + α ∀p ∈ σ and ∀q ∈ L . The set of simplices that have an α-Delaunay center in W is a simplicial complex, called the α-relaxed Delaunay complex, and is denoted Del α (L , W ).

We say w ∈ W is an α-witness for σ ⊂ L if w -p ≤ w -q + α for all p ∈ σ and all q ∈ L \ σ. We observe that w ∈ W is an α-Delaunay center if and only if it is an α-center and also an α-witness. If, for some δ ≥ 0, each of the d-simplices in Del α (L , W ) has a δ-protected circumcenter, then we have that Del α (L , W ) ⊆ Del(L ), and with α ≥ 2ε, it follows (Lemma 8) that Del α (L , W ) = Del(L ), and Del(L ) is itself δ-protected and has good links.

Reviewing the analysis of the Moser-Tardos algorithm of Section 4.2, we observe that the exact same estimate of 2 (p ) that serves as an upper bound on the probability that one of the simplices in star 2 (p , Del(L )) is not δ-protected at its circumcenter, also serves as an upper bound on the probability that one of the simplices in star 2 (p , Del α (L , T d )) is not δ-protected at its circumcenter, provided that 4α+δ ≤ λ (using the diameter bound of 2λ +2α from Lemma 8), which we will assume from now on. We can therefore modify the algorithm by replacing Wit(L , W ) by Del α (L , W ).

We now describe how to improve this algorithm to make it efficient. For our purposes it will be sufficient to set α = 2ε. In order to obtain an algorithm sublinear in |W |, we will not compute the full Del 2ε (L , W ) but only a subcomplex we call Del 2ε 0 (L , W ). The exact definition of Del 2ε 0 (L , W ) will be given in Section 5.3, but the idea is to only consider d-simplices that show the properties of being Θ 0 -thick for some parameter Θ 0 to be defined later. This will allow us to restrict our attention to points of W that lie near the circumcenter. As explained in Section 5.3, this is done without explicitly computing thickness or circumcenters.

As will be shown in Section 5.4 (Lemma 12), the modification of the witness algorithm ([6, Algo. 1]) that computes Del 2ε 0 (L , W ) instead of Wit(L , W ) will terminate and output a complex Del 2ε 0 (L , W ) with good links. However, this is not sufficient to guarantee that the output is correct, i.e., that Del 2ε (L , W ) = Del(L ). In order to obtain this guarantee, we insert an extra procedure check(), which, without affecting the termination guarantee, will ensure that the simplices of Del 2ε 0 (L , W ) have δ * -protected circumcenters for a positive δ * . It follows that Del 2ε 0 (L , W ) ⊆ Del(L ) and, by Lemma 4, that Del 2ε 0 (L , W ) = Del(L ). Pseudocode for this modified perturbation algorithm is presented as Algorithm 2 in [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF].

We describe the details of computing Del 2ε 0 (L , W ) and of the check() procedure in the following subsections.

Computing relaxed Delaunay centers

We observe that the α-Delaunay centers of a d-simplex σ are close to the circumcenter of σ, provided that σ has a bounded thickness: Lemma 9 (Clustered α-Delaunay centers). Assume that L is a (λ , μ )sample. Let σ be a non degenerate d-simplex, and let x be an α-center for σ at distance at most Cλ from the vertices of σ, for some constant C > 0. Then x is at distance at most Cα Θ(σ)μ from the circumcenter c σ of σ. In particular, if x is an α-Delaunay center for σ, then c σ -x < 2α Θ(σ)μ .

See [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF] for a proof. It follows from Lemma 9 that α-Delaunay centers are close to all the bisecting hyperplanes H pq = {x ∈ R d | x -p = x -q , p, q ∈ σ}. The next simple lemma asserts a kind of qualitative converse: Lemma 10. Let σ be a d-simplex and H pq be the bisecting hyperplane of p and q. A point x that satisfies d(x, H pq ) ≤ α, for any p, q ∈ σ is a 2α-center of σ.

Let σ be a d-simplex of Del α (L , W ) and let Ω be the smallest box with edges parallel to the coordinate axes that contains σ. Then the edges of Ω have length at most 2λ + 2α (Lemma 8). Any α-Delaunay center for σ is at a distance at most λ + α from Ω. Therefore all the α-Delaunay centers for σ lie in an axisaligned hypercube Ω with the same center as Ω and with side length at most 4λ + 4α < 5λ . Observe that the diameter (diagonal) z of Ω is at most 5λ √ d. Our strategy is to first compute the α-centers of σ that belong to Ω ∩ W and then to determine which ones are α-witnesses for σ. Deciding if an α-center is an α-witness for σ can be done in constant time since L is a (λ , μ )-net and ∆ σ ≤ 2λ + 2α (Lemma 8).

We take α = 2ε. To compute the 2ε-Delaunay centers of σ, we will use a pyramid data structure (it is an octree when d = 3). The pyramid consists of at most log z ε levels. Each level h > 0 is a grid of resolution 2 -h z. The grid at level 0 consists of the single cell, Ω. Each node of the pyramid is associated to a cell of a grid. The children of a node ν correspond to a subdivision into 2 d subcells (of the same size) of the cell associated to ν. The leaves are associated to the cells of the finest grid whose cells have diameter ε.

A node of the pyramid that is intersected by all the bisecting hyperplanes of σ will be called a full node or, equivalently, a full cell. By our definition of W , a cell of the finest grid contains an element of W at its center. The full-leaf-points In order to have δ * > 0, we need a lower bound on δ, and hence on the minimal perturbation radius through δ = Jρ. Therefore we require: Jµ 4 ≥ δ > 34 √ dε Θ0 μ (compare with (2)). Writing δ = δ λ and Θ 0 = δ μ 8d , and using λ ≥ λ, μ ≥ μ/3 when ρ ≤ µ/4, we obtain the conditions under which Algorithm 2 is guaranteed to produce a δ * -protected Delaunay triangulation: J μ 4 ≥ δ > 2448d

  (p ) -I 2 (p ) : the set of points of L that can violate the δ-protected zone Z δ (σ ) = B(c σ , R σ + δ) \ B(c σ , R σ ) for some d-simplex σ in star 2 (p ) -I(p ) := I 1 (p ) ∪ I 2 (p ) -S(p ) : the set of d-simplices with vertices in I 1 (p ) that can belong to star 2 (p )

Lemma 7 . ( 1 )

 71 |I(p )| ≤ I = 36 μ d and |S(p )| ≤ K= I d+1 (d+1)! . (2) An event is independent of all but at most Γ = 66 μ d other events. (3) 3 (q , σ ) ≤ 2π d-1 δ ρ .

Γ

  and since |I(p )| ≤ I, we get that the number of point perturbations performed by the algorithm is O I |L| Γ on expectation.

Lemma 8 .

 8 The distance between an α-Delaunay center for σ ∈ Del α (L , W ) and the farthest vertex in σ is less than λ + α. In particular, ∆ σ < 2λ + 2α.If τ ∈ Del(L ) and c is a Delaunay center of τ , then any point in B(c, r) is a 2r-Delaunay center for τ . Thus Del(L ) ⊆ Del 2ε (L , W ).

Lemma 13 .

 13 If δ = Jρ, with J defined in Eq. (2), then the d-simplices in Del 2ε 0 (L , W ) produced by the modified perturbation algorithm [6, Algo. 2] are δ * -protected, with δ * = δ -34 √ d Θ0 μ ε.

  right-hand inequality is satisfied provided δ ≥ 50d

Theorem 3 ..

 3 If ρ ≤ μ/4 and ρ = Ω 1 J μ ε λ (with J defined in Eq. (2)), Algorithm 2 terminates and outputs the Delaunay triangulation of L . The Delaunay d-simplices are δ * -protected, as defined in Lemma 13, and consequently satisfy a thickness bound of Θ(σ) ≥ δ * (μ/3+ δ * ) 8d log λ ε . The constants in Ω and O depend only on d (the dependence being exponential).

Acknowledgments

Partial support has been provided by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).

Arijit Ghosh is supported by the Indo-German Max Planck Center for Computer Science (IMPECS).

are the elements of W associated to full cells at the finest level. By Lemma 10, the full-leaf-points are 2ε-centers for σ. In order to identify the full-leaf cells, we traverse the full nodes of the pyramid starting from the root. Note that to decide if a cell is full, we only have to decide if two corners of a cell are on opposite sides of a bisecting hyperplane, which reduces to evaluating a polynomial of degree 2 in the input variables. A simple volume argument leads to the following lemma:

, where n 0 depends on d. n σ (ε) is also a bound on the time to compute the full cells. (μ ) d 2 . We then extract from C d (p ) a subset W C d (p ) of simplices that have a full-leafpoint that is a 2ε-Delaunay center, and have a number of full cells less than or equal to n 0 (ε)

Construction of Del

ε . This is done by applying the algorithm of Section 5.2 with a twist. As soon as a d-simplex appears to have more than n 0 (ε) full cells, we stop considering that simplex. The union of the sets W C d (p ) for all p ∈ L is a subcomplex of Del 2ε (L ) called Del 2ε 0 (L , W ). It contains every d-simplex σ in Del 2ε (L , W ) that has a 2ε-Delaunay center in W at a distance less than ε from its actual circumcenter, and satisfies the thickness criterion Θ(σ) ≥ Θ 0 . Note, however, that we do not claim that every simplex that has at most n 0 (ε) full cells is Θ 0 -thick. See

Correctness of the algorithm

We will need the following lemma which is an analog of Lemma 2. The lemma also fixes Θ 0 . Its proof follows directly from Lemma 3, and the observation that any simplex with a protected circumcenter is a Delaunay simplex. We first show that Algorithm 2 terminates if we desactivate the call to procedure check(). As discussed after Lemma 8, the analysis of Section 4.2 implies that the perturbations of Algorithm 2 can be expected to produce a point set L for which all the d-simplices in Del 2ε (L , T d ) have a δ-protected circumcenter. Since this complex includes both Del(L ) and Del 2ε 0 (L , W ), Lemma 12 shows that we can expect the algorithm to terminate with the condition that Del 2ε 0 (L , W ) has good links. We now examine procedure check() and show that it does not affect the termination guarantee. By Lemma 3, if Del(L ) is δ-protected, then any σ ∈ Del(L ) satisfies Θ(σ) ≥ Θ 0 = δ μ 8d . Consider now σ ∈ Del 2ε 0 (L , W ). Since the full leaves of the pyramid data-structure for σ are composed entirely of 2ε-centers at a distance less than 4 √ dλ from any vertex of σ, Lemma 9 implies that, if σ is Θ 0 -thick, then x-c σ ≤ 8 √ dε Θ0 μ . This means that we can restrict our definition of Del 2ε 0 (L , W ) to include only simplices for which the set of full leaves has diameter less than 16 √ dε Θ0 μ . Further, we observe that if σ is δ-protected at its circumcenter, then it will have a (δ -2ε)-protected full-leaf-point; this follows from the triangle inequality. The check() procedure ensures that all the simplices in Del 2ε 0 (L , W ) have these two properties. It follows from the discussion above that activating procedure check() does not affect the termination guarantee.

The fact that the algorithm terminates yields Del 2ε 0 (L , W ) with good links. In order to apply Lemma 12 to guarantee that Del 2ε 0 (L , W ) = Del(L ), we need to guarantee that the simplices of Del 2ε 0 (L , W ) are protected. The following lemma, proved in [START_REF] Boissonnat | A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations[END_REF], provides a bound on δ to ensure such a protection δ * > 0.