Introduction

Given a planar subdivision of size n, the point location problem consists of determining the face of the subdivision that contains a given query point. Since any planar subdivision can be triangulated, focusing on the special case of triangulation is not restrictive. This is a classic problem in computational geometry and has received a lot of attention in the literature. It is a well known fact that it is possible to build an O(n) size data structure that permits queries in O(log n) worst case time [START_REF] Kirkpatrick | Optimal search in planar subdivisions[END_REF][START_REF] Preparata | Planar point location revisited[END_REF][START_REF] Preparata | Computational Geometry: An Introduction[END_REF]. However, although theoretically optimal from the asymptotic worst case point of view, these methods rely on complicated data structures and often hide big constants in the big-O notation. In practice simpler strategies are often preferred, such as walking strategies [START_REF] De Castro | Simple and efficient distribution-sensitive point location, in triangulations[END_REF][START_REF] Devillers | Walking in a triangulation[END_REF][START_REF] Lawson | Software for C 1 surface interpolation[END_REF] or their derivatives [START_REF] Devillers | The Delaunay hierarchy[END_REF][START_REF] Devroye | A note on point location in Delaunay triangulations of random points[END_REF].

Walking strategies can be used to solve the point location problem by exploring the triangulation using neighbour relationships to move incrementally closer to the query point. These strategies can be classified into two main categories depending on whether the walk moves between the vertices or between the triangles. For each category, there are still many ways to initialise the walk, and also multiple ways to choose which neighbour is taken at each step in the walk.

The worst case analysis of walking strategies is usually of little practical interest, since pathological examples with exponential behaviour can be constructed that do not occur in practice. In the important case of Delaunay triangulation, the worst case walk remains of linear complexity [START_REF] Devillers | Walking in a triangulation[END_REF]. It is conjectured that walking strategies require O( √ n ) steps in expectation when walking in the Delaunay triangulation of n points uniformly distributed in a square. Such a result has been formally demonstrated in the special case of the straight walk strategy by Devroye et al. [START_REF] Devroye | Expected time analysis for Delaunay point location[END_REF]. The straight walk strategy [START_REF] Devillers | Walking in a triangulation[END_REF] consists in moving towards the destination by walking through all the triangles intersected by the line segment between the start point and the query point. The analysis of straight walk is also related to the stabbing number of the Delaunay triangulation. Bose and Devroye [START_REF] Bose | On the stabbing number of a random Delaunay triangulation[END_REF] have proved that the maximum number of triangles intersected by any straight line in the Delaunay triangulation of a set of n independent uniformly random points in the square is O( √ n ), which clearly implies that the cost of the straight walk between any pair of points is O( √ n ) [see also [START_REF] Pimentel | Greedy polyominoes and first-passage times on random Voronoi tilings[END_REF].

The straight walk is easier to analyse than other strategies because the probability that a random triangle is part of the walk depends only on the triangle and the line segment, in particular it does not depend on the position of the other vertices. For other strategies, such as visibility walk [START_REF] Devillers | Walking in a triangulation[END_REF], the behaviour of a given step in the walk may be dependent on a previous part of the walk, which makes the analysis more intricate. Such an O( √ n ) result for visibility walk is still an open problem to our knowledge. 1 Routing in sensor networks is another important application of walking strategies [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF][START_REF] Misra | Guide to wireless sensor networks[END_REF][START_REF] Zhao | Wireless Sensor Networks. An Information Processing Approach[END_REF]. In this case however, the destination is usually a vertex of the triangulation. In the context of 1 Zhu provides a tentative proof of a O √ n log n bound for visibility walk [START_REF] Zhu | On Lawson's oriented walk in random Delaunay triangulations[END_REF]. This proof is a proof by induction for "a random edge at distance d", it consider the next edge in the walk and apply the induction hypothesis to this new edge computing the new distance. Unfortunately, the new edge cannot be considered at random, it is an edge obtained by the walk algorithm and the edges have not the same probability to be the second (or k th ) edge of the walk. Restarting the walk from a given edge is not either possible (as done in [START_REF] Zhu | On Lawson's oriented walk in random Delaunay triangulations[END_REF]) since the knowledge that this edge is a Delaunay edge as an influence on the point distribution.

Inria routing, we are also interested in the quality of the strategy in terms of the total length of the edges used relative to the Euclidean distance between the departure and destination points. Very recently some interesting results have been obtained when the underlying graph is the half-θ 6 graph introduced by Bonichon et al. [START_REF] Bonichon | Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces[END_REF]. This graph is similar to the Delaunay triangulation, with the empty circle property replaced by an empty equilateral triangle. In particular, Bose et al. [START_REF] Bose | Competitive routing in the half-θ 6 -graph[END_REF] have devised routing algorithm which is optimal with respect to the length of the path.

When the point set is random, Bonichon and Marckert [START_REF] Bonichon | Asymptotics of geometrical navigation on a random set of points in the plane[END_REF] and Bordenave [START_REF] Bordenave | Navigation on a Poisson point process[END_REF] have studied various navigation procedures based on finding good neighbours in certain sectors. See also [START_REF] Baccelli | The radial spanning tree of a Poisson point process[END_REF] where a radial spanning tree is constructed, which may be seen as the tree of all paths to a specific target. In the case of Delaunay triangulations, the structure of the graph makes the probabilistic analysis more complex, and much less is known. Many routing strategies have been studied by Bose and Morin [START_REF] Bose | Online routing in triangulations[END_REF], but they mostly focus on which algorithms will find a correct path in any Delaunay triangulation using only local information.

In this paper we focus our attention on vertex walking strategies. In particular we consider the class of closer vertex walks, which is the class of walks that always move strictly closer to the destination at each step. Such a walk is guaranteed to reach the closest neighbour of the query if the triangulation is Delaunay. A well known closer vertex walk is the closest vertex walk which chooses the Delaunay neighbour that is closest to the destination at each step. To our knowledge, there is no proof that the closest vertex walk or any other vertex walking strategy finds the query point in O( √ n ) expected time.

Contribution.

In this paper we focus on Delaunay triangulations of random points, and we analyse a particular closer vertex walk which we refer to as cone walk. For this strategy, we select the next vertex from a pre-defined region directed towards the query. In this case, we provide a thorough analysis of the walk; quantifying many properties of the path produced (number of visited sites, stretch factor) and of the algorithm (number of steps, complexity) for a given starting point and query. When computing the complexity of the resulting algorithm we must take care, since to choose the next vertex at each step we will need to examine all of the neighbours of several vertices. For this reason we additionally compute the sum of the degrees over all of the vertices visited during the walk. We show that this does not affect the asymptotic running time of the algorithm by providing an expected O( √ n ) time bound. More specifically, we provide performance guarantees by proving that for every possible start point and every possible query point, the walk will always finish in expected time O( √ n ). This result is formalised in the following theorem. Let D be a smooth convex domain of the plane with area 1, and write D n = √ nD for its scaling to area n.

Theorem 1. Consider Φ n a Poisson point process of intensity 1 in the smooth convex domain D n of area n. Let Γ(z, q) denote either the Euclidean length of the path generated by the cone walk from z ∈ Φ n to q ∈ D n , its number of edges, or the cost of the algorithm to generate it. Then there exist constants C Γ,D and A Γ,D depending only on Γ and on the shape of D such that

P sup z∈Φ n , q∈Dn Γ(z, q) > C Γ,D √ n ≤ A Γ,D e -log 3/2 n
, and

E sup z∈Φ n , q∈Dn Γ(z, q) = O( √ n ).
Stopper y r Disc(z, q, r)

π 8 z q
Cone(z, q, r)

w

Algorithm and geometric properties

We consider the finite set of sites in general position, X ⊂ R 2 contained within a compact convex domain D ⊂ R 2 . Let DT(X) be the Delaunay triangulation of X, which is the graph in which three sites x, y, z ∈ X form a triangle if and only if the disk with x, y and z on its boundary does not contain any site in X. Given two points z, q ∈ R 2 and a number r ∈ R we define Disc(z, q, r) to be the closed disc whose diameter spans z and the point at a distance 2r from z on the line zq. Finally, we define Cone(z, q, r) to be the sub-region of Disc(z, q, r) contained within a closed cone of apex z, axis zq and half angle π 8 (see Figure 1).

The cone walk algorithm

Given a site z ∈ X and a destination point q ∈ D, we fix one step of the cone walk algorithm by growing the region Cone(z, q, r) anchored at z from r = 0 until the first point y ∈ X is found such that the region is non-empty. Once y has been determined, we refer to it as the stopper. We call the region Cone(z, q, r) for the given r a search cone, and we call the associated disc Disc(z, q, r) the search disc. The point y is then selected as the next step and the walk continues. In Lemma 2 we show that there exists a path between z and y entirely contained within Disc(z, q, r) and following adjacency relations in DT(X).

We terminate the process when the destination q is contained within the search disc for a given step. At this point we know that one of the points contained within Disc(z, q, r) is a Delaunay neighbour of q in DT(X ∪ {q}). We can further compute the face containing the query point q (point location) or find the nearest neighbour of q in DT(X) by simulating the insertion of the point q into DT(X) and performing an exhaustive search on the neighbours of q in DT(X ∪ {q}).

We now show that we can compute cone walk efficiently using only local information in the triangulation at each step. This is achieved by following a series of intermediate steps corresponding to points of X in the search disc for each step. The Delaunay property ensures that the required steps are always Delaunay neighbours of previously visited points (see correctness below).

Inria

The pseudo-code below gives a detailed algorithmic description of this procedure. The algorithm will take as input some z ∈ X, q ∈ D and return a Delaunay neighbour of q in DT(X ∪ {q}). We also print a path in the triangulation which is completely contained within the search discs for each step.

NEXT-VERTEX(S, z, q) Where we define the following predicates:

1 r = ∞ 2 for (u ∈ S) 3 if GET-RADIUS(z, q, u) < r 4 y = u 5 r = GET-RADIUS(z, q, u) 6 return y CONE-WALK(z, q) 1 SubSteps = {z} 2 print z 3 Candidates = NEIGHBOURS(z) in DT(X) 4 P redecessor[ ] = ⊥ //
IN-CONE(z, q, y) := 1 (y -z) • (q -z) y -z q -z > 2 + √ 2 2 GET-RADIUS(z, q, u) := 1 2 q -u 2 - (q -z) • (q -u) q -z 2
Lines 11 to 20 and the P redecessor[ ] table are only required for computing a path on the edges of the Delaunay triangulation contained within the search disks (see Figure 2). If this is not required these steps can be omitted so that the procedure just performs point location and returns a neighbour of q in DT(X ∪ {q}).

Correctness. On every iteration of the main loop at line 6, we maintain a current vertex z ∈ X, an intermediary point y ∈ X ∪ {q}, a set SubSteps ⊂ X that contains all points in Disc(z, q, r) (for r such that y ∈ ∂Disc(z, q, r)) and a set Candidates ⊂ X that contains all Delaunay neighbours of points in Disc(z, q, r) that have not already been visited. These conditions are certainly true at the beginning of each step, and to see that they remain true on further iterations it suffices to note that the point y defining the next largest search disc, Disc(z, q, r ), is always contained in Candidates as a direct consequence of Lemma 2. This lemma also guarantees that the destination point is a Delaunay neighbour of a site contained in the final search disc on termination.

For the path, note that we mark every site accessed with the intermediary vertex that we first accessed it from during the current step. We call such a point a predecessor. Since we visit all points within the search disc at the end of the step, and we only marked sites with sites that are Delaunay neighbours, following the path of predecessors must result in a path in the triangulation.

Complexity. We consider only the number of operations required to complete one step in the walk, since the number of steps required is dependent on the point distribution. In later sections we provide an analysis for the number of steps given certain distribution assumptions. We proceed by noting that on every intermediary step, we visit all of the neighbours of all of the points contained within the search disc Disc(z, q, r), where r is the final radius for the step. Hence we may require Θ(km) operations to complete one step, where k is the number of points in Disc(z, q, r) and m is the number of such points along with all their neighbours. An insertion into Candidates corresponds to an oriented edge that intersects Disc(z, q, r) and so by Euler relation there are fewer than 6m such edges. If insertions into Candidates are done in constant time and we retrieve the minimum in linear time, we get the claimed complexity. We can improve on this by storing the Candidates in a priority queue keyed on the associated search-disc radius of each point, giving us an easy improvement to O(m log m). We observe that y is always a Delaunay neighbour of at least one of the points contained within the region Disc(z, q, r), where r is the radius ensuring y ∈ ∂Disc(z, q, r).

Inria q Z 0 Z 1 Z 2 Z 3 Z 4 Z κ-1 R 1 S 1

Geometric properties 2.2.1 Finding a Delaunay path within the discs

Lemma 2 (Path finding lemma). Let q ∈ D, z ∈ X and y, y ∈ X with associated discs satisfying Disc(z, q, r) ⊂ Disc(z, q, r ) and (Disc(z, q, r ) \ Disc(z, q, r)) ∩ X = {y}. Then there exists a point in Disc(z, q, r) that is a Delaunay neighbour of y .

Proof. Let γ be the centre of Disc(z, q, r ). We grow Disc(y , γ , ρ) ⊂ Disc(z, q, r ) until we hit a point w in X. w is always contained within Disc(z, q, r) because z is on the border of Disc(z, q, r). Since the disc is empty this must be a Delaunay neighbour of y . See Figure 3.

Corollary 3. Let q ∈ D, z ∈ X with y ∈ X its associated stopper satisfying y ∈ ∂Cone(z, q, r). Then there is a path of edges of DT(X) between z and y contained within Disc(z, q, r). Cone(y, q, ∞)

π 4 π 8 y r Disc(z, q, r) π 8 z π 8 -β q z Cone(z, q, r)

Independence of the search cones

When growing the search cone, it is important to observe that each new search cone does not overlap previous ones, except at the very end of the walk. This is formalised by the following lemma.

Lemma 4 (Non-overlapping lemma). Let z and y be two points of X and r > 0 such that Cone(z, q, r) has y on its boundary. If zq > (2 + √ 2 )r then Disc(z, q, r) does not intersect the search cone Cone(y, q, ∞) issued from y nor any other search cone for any subsequent step of the walk.

Proof. Assume without loss of generality that y lies to the left of line zq and consider the construction given in Figure 4. Let β denote the angle between the tangent to Disc(z, q, r) at y and the ray bordering Cone(y, q, ∞). Cone(y, q, ∞) and Disc(z, q, r) do not intersect provided that β ≥ 0. Placing y at the corner of Cone(z, q, r) maximizes β, in which case we have β > 0 if and only if q is to the right of z , the point symmetrical to z with respect to the line through y perpendicular to zq. Elementary computations then yield the result. Since the whole sequence of search cones following the one issued from y remains in Cone(y, q, ∞), Disc(z, q, r) does not intersect any of these search cones, and the result follows.

Independence of the search discs

When growing the search disc region, the new search disc may overlap previous search discs but only in their cone parts. This is formalised by the following lemma: Lemma 5 (Overlapping lemma). Let z and y be two points such that Cone(z, q, r) has y on its boundary. Then if the search disc Disc(y, q, ∞) issued from y does not contain q, it does not intersect Disc(z, q, r) \ Cone(z, q, r).

Proof. By symmetry we observe that Disc(y, q, ρ) only intersects the point y , the point y reflected through the line zq, when the centre of Disc(y, q, ρ) coincides with q (See Figure 5). Inria Disc(z, q, r) z Cone(z, q, r) q Disc(y, q, ρ) y y ρ ρ Cone(y, q, ρ) Disc(z, q, r) ∩ Disc(y, q, ρ) ⊂ Cone(z, q, r) Since the algorithm terminates as soon as the current search disc touches q, q is never contained within Disc(z, q, ∞) and thus this can never happen.

Stability of the walk

In the following lemma we are interested in the stability of the sequence of steps to reach q. Lemma 6 (Invariance lemma). There exists a partition in the plane with fewer than n 4 cells such that the sequence of steps used by the cone walk algorithm from any vertex of the triangulation does not change when q moves in a region of the partition.

Proof. Take a point z ∈ X and consider S z , the set of all possible stoppers defined by Cone(z, q, r) for some q ∈ D and r > 0. Each s ∈ S z defines a unique sector about z such that moving a point in the given sector does not change the stopper (see Figure 6). We then create an arrangement by adding a ray on the border of every sector for each point z ∈ X. The resulting arrangement has the property that moving the destination point q within one of the cells of the arrangement does not change the stopper of any step for any possible walk. Clearly, |S z | ≤ n -1 for all z ∈ X, and thus there are at most n(n -1) rays in the arrangement. Since an arrangement of m lines has at most m2 +m+2 2 cells the result follows [see, e.g., 19, p. 127].

The cone walk for the Poisson Delaunay in a disk

Our aim in this section is to prove the main elements towards Theorem 1, which we go on to complete in Section 4. Our ultimate goal is to prove bounds on the behaviour of the cone walk for the worst possible pair of starting point and query. Achieving this requires strong bounds on the probability that the walk behaves badly for a fixed start point and query. Note that, by Lemma 6, although the query is taken from an uncountable set, the number of start/query pairs which matter has size between 2 O(n 5 ) and Ω(n 2 ). This number is too large to be taken care of by the tail bounds derived from Markov or Chebyshev's inequalities together with mean or variance estimates, and thus we need to resort to stronger tools.

Our techniques rely on concentration inequalities [START_REF] Boucheron | Concentration Inequalities -A nonasymptotic theory of independence[END_REF][START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF][START_REF] Janson | Large deviation for sums of partially dependent random variables[END_REF][START_REF] Mcdiarmid | Concentration[END_REF]. Most of the bounds we obtain (for the number of steps κ and the number of visited sites) follow from a representation as a sum of random variables in which the increments can be made independent by a simple and natural conditioning. The bounds on the complexity of the algorithm CONE-WALK are slightly trickier to derive because there is no way to make the increments independent.

For the sake of presentation, we start by studying the walk in the disc D n of area n where the query is at the centre. These choices for D n and q ensure that for any z ∈ D n and any r ≤ n/π, we have Disc(z, q, r) ⊂ D n . We then relax these constraints in Section 4. Let Φ be generated by a planar Poisson process of rate 1 in D n and consider DT(Φ). In practice, the Delaunay triangulation is accessed by using a handle to the data structure, here we assume we are given a pointer to one of the vertices. For z ∈ D n , we let Φ z be Φ conditioned to have a point located at z. Classical results on Poisson point processes ensure that Φ z \{z} is distributed like Φ, so that one can take Φ z = Φ ∪ {z} [see, e.g., 1, Section 1.4].

Preliminaries

We establish the following notation (see Figure 2). Let Z = (Z i , i ≥ 0) denote the sequence of stoppers which are visited during the walk, and write L i = Z i q for the distance to the query. The distance L i is strictly decreasing and the point set Φ is almost surely finite, thus ensuring that the walk stops after a finite number of steps κ, at which point we have Z κ = q. For x > 0, we also let κ(x) be the number of steps required to reach a point within distance x of the query. Therefore i < κ(x) if and only if L i > x. The important parameters needed to track the location and progress of the walk are the radius R i such that Z i+1 ∈ ∂Cone(Z i , q, R i ), and the angle α i between Z i q and Z i Z i+1 . Disc(Z i , q, R i ) may contain several points of Φ, let τ i denote | Disc(Z i , q, R i ) \ {Z i , Z i+1 } ∩ Φ| the number of such points and N i the number of these points along with their Delaunay neighbours.

In order to compute the walk efficiently, the algorithm presented gathers a lot of information. In particular, we access all of the points in Disc(Z i , q, R i ) and their neighbours. For the analysis, we want to keep the landscape as concise as possible, and so we define a filtration which only contains the necessary information for the walk to be a measurable process. Let F i denote the information consisting of (the σ-algebra generated by) the locations of the points of Φ contained in ∪ i j=0 Disc(Z j , q, R j ).

If the search cone Cone(Z i , q, ∞) does not intersect any of the previous search cones, the region which determines R i+1 is "fresh" and R i+1 is independent of F i . Lemma 4 provides a condition which guarantees independence of the search cones. Write ξ := 2 + √ 2.

To take advantage of it, for i ≥ 0, define the event

G i := {∀j ≤ i + 1, R j < ω n /ξ}, (1)
where from now on we shall write ω n to denote a sequence satisfying ω n ≥ log n. Then on G i := G i ∩ {L i ≥ ω n }and for every j ≤ i, the search-cone Cone(Z j , q, ∞) does not intersect any of the regions Disc(Z k , q, R k ), 0 ≤ k < j, and the corresponding variables (R j , α j ), 0 ≤ j ≤ i + 1 are independent. Although it might seem like an odd idea, G i does include some condition on R i+1 ; this is mostly to ensure that on G i , we have L i+1 > L i -2R i+1 > 0, so that i + 1 is not the last step. So for x > 0:

P(R i+1 ≥ x | F i , G i ) = P(Φ ∩ Cone(Z i , q, x) = ∅ | F i , G i )1 {ξx≤ωn} = e -Ax 2 1 {ξx≤ωn} , (2)
where A denotes the area of Cone(z, q, 1), which is the shaded region in Figure 1. Indeed, conditional on F i and G i , |Φ ∩ Cone(Z i , q, x)| is a Poisson random variable with mean Ax 2 where

A := 2 cos π 8 sin π 8 + π 8 = √ 2 2 + π 4 . (3)
It is convenient to work with an "ideal" random variable that is not constrained by the location of the query, and we define R by the distribution P(R ≥ x) = e -Ax 2 for x ≥ 0.

To compute the distribution of the angle, let Cone α (z, q, r) be the cone of half angle α with the same apex and axis as Cone(z, q, r). For S ⊂ R 2 , let A(S) denote its area. On the event G i , Z i+2 = q and α i+1 is truely random and its distribution is symmetric and given by (see Figure 7)

P(|α i+1 | < x | R i+1 = r, F i , G i ) = lim ε→0 A(Cone x (Z i , q, r + ε) \ Cone x (Z i , q, r)) A(Cone(Z i , q, r + ε) \ Cone(Z i , q, r)) = lim ε→0 ((r + ε) 2 -r 2 )(x + 1 2 sin 2x) ((r + ε) 2 -r 2 )( π 8 + √ 2 4 ) = 8 π + 2 √ 2 x + sin 2x 2 . ( 4
) α r r+ε π 8
Figure 7: For the angle to be smaller than α given R ∈ [r, r + ε], the stopper must fall within the dark shaded region So in particular, conditional on F i and G i , α i+1 is independent of R i+1 . We will write α for the "ideal" angle distribution given by (4), and enforce that R and α be independent. We will repeatedly use the conditioning on G i to introduce independence, and it is important to verify that G i indeed occurs with high probability. For G i to fail, there must be a first step j at which R j ≥ ω n is too large. Writing G c i for the complement of G i and defining G -1 to be a void conditioning: provided that i = O(n) (which will always be the case in the following)

Z i+1 Z i q L i+1 L i π 8 α i 2α i
P(G c i ) ≤ 0≤j≤i+1 P(R j ≥ ω n | G j-1 ) ≤ e log O(n)-Aω 2 n /ξ 2 ≤ e -ω 3/2 n ( 5
)
for all n large enough, since writing Po(x) for a Poisson random variable with mean x we have P(Po(n) ≥ 2n) ≤ exp(-n/3) and ω n ≥ log n.

Geometric and combinatorial parameters

Recall that L i = Z i q and α i denotes the angle between Z i Z i+1 and Z i q. Simple geometry implies that (see Figure 8):

Inria L i -R i (1 + cos(2α i )) ≤ L i+1 = (L i -R i (1 + cos(2α i ))) 2 + R 2 i sin 2 (2α i ) ≤ L i -R i (1 + cos(2α i )) + 2 R 2 i L i , (6) since
√ 1 -x ≤ 1 -x/2 for any x ∈ [0, 1]. As a consequence L 0 - i-1 j=0 R i (1 + cos(2α i )) ≤ L i ≤ L 0 - i-1 j=0 R i (1 + cos(2α i )) + 2 ω n • i-1 j=0 R 2 i . (7)
In particular, since ω n → ∞, after i steps, the expected distance E[L i ] to the aim should not be far from L 0 -iE[R(1 + cos(2α))]. Furthermore, conditional on G i , and for i such that L i ≥ ω n , the summands involved in Equation ( 7) are independent, bounded by 2ω n and have bounded variance, so that the sum should be highly concentrated about its expected value [START_REF] Boucheron | Concentration Inequalities -A nonasymptotic theory of independence[END_REF][START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF][START_REF] Mcdiarmid | Concentration[END_REF]. In other words, one expects that for i much larger than L 0 /E[R(1 + cos 2α)], it should be the case that L i ≤ ω n with fairly high probability. Making this formal constitutes the backbone of our proofs.

We start with a first crude estimate the the decrease in distance after a given number of steps.

Lemma 7. Let z ∈ D, suppose that ≥ 1 is such that L 0 = zq ≥ (2 + 1)ω n . Consider DT(Φ z ).
There exists a constant η > 0 such that

P (L 0 -L ≤ E[R]/2) ≤ e -η /ωn .
Proof. We use the crude bounds R i ≤ L i -L i+1 ≤ 2R i (see Figure 8). It follows that

P(L 0 -L ≤ E[R]/2) ≤ P(L 0 -L ≤ E[R]/2 | G ) + P(G c ) ≤ P -1 j=0 R j ≤ 2 E[R] G + P(R ≥ ω n ).
Now, since L 0 ≥ (2 + 1)ω n , on the event G , we have L i ≥ ω n for 0 ≤ i ≤ so that G occurs: conditional on G , the search cones do no intersect and random variables R j , 0 ≤ j ≤ are independent and identically distributed. Furthermore, we have

E[R j | G ] = ωn 0 P (R j ≥ x | G ) dx ≥ ωn 0 (e -Ax 2 -e -Aω 2 n /ξ 2 )dx ≥ E[R] -e -ω 3/2 n ,
for all n large enough. It follows that for all n large enough, by Theorem 2.7 of [20, p. 203]

P -1 j=0 R j ≤ 2 E[R] G ≤ P -1 j=0 (R j -E[R j | G ]) ≤ -3 E[R 0 | G ] G ≤ exp - t 2 2 V(R 0 | G ) + 2tω n /3 t = E[R 0 | G ]/3 ≤ exp(-η /ω n ),
for some constant η > 0.

The rough estimate in Lemma 7 may be significantly strengthened, and the very representation in [START_REF] Bose | Online routing in triangulations[END_REF] yields a bound on the number of search cones or steps that are required to get within distance ω n of the query point q. (If the starting site z satisfies L 0 = zq ≤ ω n , then this phase does not contain any step.) Proposition 8. Let z ∈ D n , and let κ(ω n ) denote the number of steps of the walk to reach a site which is within distance ω n of q in DT(Φ z ∪ {q}) when starting from the site z ∈ Φ z at distance L 0 = zq ≥ ω n . Then

P κ(ω n ) - L 0 E[R(1 + cos 2α)] ≥ 2ω 2 n 2L 0 + ω n ≤ 4 exp(-ω 3/2 n ).
Proof. We start with the upper bound. We now make formal the intuition that follow Equation [START_REF] Bose | Online routing in triangulations[END_REF]. For any integer k, we have

P (κ(ω n ) ≥ k) = P (L k ≥ ω n ) ≤ P (L k ≥ ω n | G k ) + P (G c k ) ,
and since the second term is bounded in [START_REF] Bordenave | Navigation on a Poisson point process[END_REF], it now suffices to bound the first one. However, given G k and L k ≥ ω n , the random variables (R i , α i ), i = 1, . . . , k are independent and identically distributed. The only effect of this conditioning is that

R i is distributed as R conditioned on R < ω n /ξ. Write X i = R i (1 + cos 2α i ) -2R 2 i /ω n .
Then, from (7), we have

P (L k ≥ ω n | G k ) ≤ P k-1 i=0 X i ≤ L 0 -ω n G k .
Conditional on G k , the random variables X i are independent, 0 ≤ X i ≤ 2R i ≤ ω n . Furthermore, since X i has Gaussian tails, its variance (conditional on G k ) is bounded by a constant independent of n.

Choosing k 0 = (L 0 + t)/E[X 0 | G 0 ]
, for some t < L 0 to be chosen later, and using the Bernstein-type inequality in Theorem 2.7 of [20, p. 203], we obtain

P(L k 0 ≥ ω n | G k 0 ) ≤ P k 0 -1 i=0 (X i -E[X i | G k 0 ]) ≤ -t G k 0 ≤ exp - t 2 2k 0 V(X 0 | G 0 ) + 2ω n t/3 .

Inria

In particular, for t = ω 3 n √ L 0 , we have for all n large enough P (L

k 0 ≥ ω n | G k 0 ) ≤ exp(-ω 2 n ), since L 0 ≥ ω n .
A matching lower bound on κ(ω n ) may be obtained similarly, using the lower bound on L i+1 in Equation ( 6) and following the approach we used to devise the upper bound with X i = R i (1 + cos 2α i ) (We omit the details.) It follows that, for k 1 = (L 0 + t)/E[X 0 | G 0 ] , we have

P(L k 1 ≤ ω n | G k 1 ) ≤ exp(-ω 2
n ). To complete the proof, it suffices to estimate the difference between k 0 and k 1 . We have

E[X 0 | G 0 ] = E[R 0 (1 + cos 2α 0 ) | G 0 ] - 2E[R 2 0 | G 0 ] ω n = E[R(1 + cos 2α)] + O(1/ω n ), and similarly, E[X 0 | G 0 ] = E[R(1 + cos 2α)]. It follows that |k 1 -k 0 | = O(L 0 /ω n ),
which is not strong enough to prove the claim, and we need to strengthen the upper bound on the second sum in the right-hand side of [START_REF] Bose | Online routing in triangulations[END_REF]. We quickly sketch how to obtain the required estimate. The idea is to use a dyadic argument to decompose κ(ω n ) into the number of steps to reach L 0 /2 j , for j ≥ 1, until one gets to ω n for j = j 0 := log 2 (L 0 /ω n ) . For the steps i which are taken from Z i with L i /L 0 ∈ (2 -j , 2 -j+1 ], we use the improved bound

L i+1 ≤ L i -R i (1 + cos 2α) + 2 L 0 2 -j R 2 i .
Then write

κ(ω n ) = j 0 j=1 κ(L 0 /2 j ) -κ(L 0 /2 j-1 ),
and observe that the j-th summand is stochastically dominated by κ(L 0 /2) where L 0 = L 0 /2 j-1 .

For each j, we define k 0 (j) = (L 0 /2 j + t j )/E[X 0 | G 0 ] where t j := ω 2 n L 0 /2 j and note that

j 0 j=1 k 0 (j) ≤ 1 E[X 0 | G 0 ] j 0 j=1 (L 0 /2 j + t j ) + log 2 (L 0 /ω n ) ≤ L 0 E[X 0 | G 0 ] + 2ω 2 n 2L 0 + ω n , for ω n ≥ log n, since πL 2 0 ≤ n. In other words, if κ(L 0 /2 j ) -κ(L 0 /2 j-1 ) ≤ k 0 (j) for every j, then κ(ω) ≤ L 0 /E[X 0 | G 0 ] + 2ω 2 n √ 2L 0 + ω n .
The claim follows easily by using the union bound, where in each stretch [L 0 /2 j , L 0 /2 j-1 ) we bound the number of steps using the previous arguments.

Corollary 9. Let z ∈ D n , and let κ denote the number of steps of the walk to reach the objective q in DT(Φ z ∪ {q}) when starting from the site z ∈ Φ z at distance L 0 = zq ≥ ω n . Then

P κ > L 0 E[R(1 + cos 2α)] + 2ω 2 n 2L 0 + ω 3 n ≤ 5 exp(-ω 3/2 n ).
Proof. It suffices to bound the number of steps i such that L i < ω n . Since L i is decreasing, the walk only stops at most once at any given site, and the number of steps i with L i ≤ ω n is at most the number of sites lying within distance ω n of q. Let Po(x) denote a Poisson random variable with mean x. We have [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF] P #{i < κ :

L i ≤ ω n } ≥ 2πω 2 n ≤ P Po(πω 2 n ) ≥ 2πω 2 n ≤ exp(-πω 2 n /3).
The claim then follows from the upper bound in Proposition 8.

Proposition 8 is the key to analyse the path constructed by the walk: representations based on sums of random variables similar to the one in ( 6) may be obtained to upper bound the number of steps and intermediate steps visited by the walk (which is an upper bound on the vertices visited by the path), and the sum of the length of the edges. Proposition 10. Let K = K(z) be the number of sites visited by the walk starting from a given site z with L 0 = zq . Then, for all n large enough,

P K ≥ L 0 E[R(1 + cos 2α)] • π -A A + L 0 ω 4 n + ω 3 n ≤ 7 exp(-ω 3/2 n ).
Proof. There are two contributions to Kκ(ω n ): first the number of intermediate steps which lie at distance greater than ω n from q, and all the sites which are visited and lie within distance ω n from q. Let K = K 1 + K 2 where K 1 and K 2 denote these two contributions, respectively. By the proof of Corollary 9, we have

P K 2 ≥ 2πω 2 n ≤ exp(-πω 2 n /3). ( 8
)
To bound K 1 , observe that the monotonicity of L i implies that K 1 counts precisely the number of intermediate steps before reaching the disc of radius ω n about q. Observe that if L 0 < ω n , K 1 = 0, so we may assume that L 0 ≥ ω n . Recall that τ i denotes the number of intermediate points at the i-th step. Note that the intermediate points counted by τ i all lie in Disc(Z i , q, R i ) \ Cone(Z i , q, R i ), and given the radius R i , τ i is stochastically bounded by a Poisson random variable with mean (π -A)R 2 i . Furthermore, on the event G κ(ωn) , the random variables R i , i = 0, . . . , κ(ω n ) are independent. Furthermore, by Lemma 5 the regions Disc(Z i , q, R i )\Cone(Z i , q, R i ), i ≥ 0, are disjoint so that the random variables τ i , i = 0, . . . , κ are independent given R i , i = 0, . . . , κ.

Let R i , i ≥ 0, be a sequence of i.i.d. random variables distributed like R conditioned on R ≤ ω n /ξ and given this sequence, let τi , i ≥ 0, be independent distributed like Po((π -A) R i ). As a consequence of the previous arguments, for

k = k 0 + 2ω 2 n √ 2L 0 + ω n with Inria k 0 = L 0 /E[R(1 + cos 2α)] ,
we have

P (K 1 ≥ ) ≤ P (k-1)∧κ(ωn) i=0 τ i ≥ + P κ(ω n ) ≥ k 0 + 2ω 2 n 2L 0 + ω n ≤ P k-1 i=0 τi ≥ + P(G c k ) + P κ(ω n ) ≥ k 0 + 2ω 2 n 2L 0 + ω n ≤ P k-1 i=0 τi ≥ + 5 exp(-ω 3/2 n ), (9)
by ( 5) and Proposition 8. We now bound the first term in [START_REF] Boucheron | Concentration Inequalities -A nonasymptotic theory of independence[END_REF]. Note that i ≥ 0, we have

E[τ i ] = (π -A)E[ R 2 i ] ≤ (π -A)E[R 2 ] = π -A A =: γ,
and we expect that k-1 i=0 τi should not exceed its expected value, kγ by much. Write = kγ +t, for some t to be chosen later. For the sum to be exceptionally large either the radii of the search disks are large, or the disks are not too large but the number of points are:

P k-1 i=0 τi ≥ kγ + t = P Po (π -A) k-1 i=0 R 2 i ≥ kγ + t ≤ P Po kγ + t 2 ≥ kγ + t + P k-1 i=0 R 2 i ≥ kγ + t/2 π -A . (10)
The first term simply involves tail bounds for Poisson random variables. For t = √ L 0 ω 4 n , we have

P Po kγ + t 2 ≥ kγ + t ≤ exp - (t/2) 2 3(kγ + t/2) ≤ exp(-ω 3 n ),
for n large (recall that we can assume here that L 0 ≥ ω n .) The second term in [START_REF] De Castro | Simple and efficient distribution-sensitive point location, in triangulations[END_REF] is bounded using the same technique as in the proof of Proposition 8 above. Since we have 0

≤ R 2 i ≤ ω 2 n and E[ R 2 i ] ≤ 1/A
, we obtain for some positive constant c,

P k-1 i=0 R 2 i ≥ kγ + t/2 π -A ≤ exp - ct 2 kV(R) + ω 2 n t .
Recalling that L 0 ≥ ω n , yields

P k-1 i=0 τi ≥ kγ + ω 4 n L 0 ≤ exp(-ω 2 n ),
for all n large enough, which together with (9) proves that

P K 1 ≥ kγ + ω 4 n √ L 0 ≤ 6e -ω 3/2
n . Using (8) readily yields the claim. Proposition 11. For z ∈ D, let Λ = Λ(z) be the sum of the lengths of the edges of DT(Φ z ) used by the walk with objective q and starting from z such that L 0 = zq . Then,

P Λ ≥ cL 0 + (3 L 0 + 1)ω 4 n ≤ 8 exp(-ω 3/2 n ) where c := 22π -4 √ 2 2 + 3π + 8 √ 2 . (11)
Proof. Write λ i for the sum of the lengths of the edges used by the walk to go from Z i to Z i+1 . So Λ = κ-1 i=0 λ i . Our bound here is very crude: all the intermediate points remain in Disc(Z i , q, R i ), and given R i , we have λ i ≤ (1 + τ i ) • 2R i . Again, on G k the cones do not intersect provide that L k ≥ ω n , and by Lemma 5 the random variables λ i , 0 ≤ i < k are independent. We use once again the method of bounded variances (Theorem 2.7 of [START_REF] Mcdiarmid | Concentration[END_REF]).

We decompose the sum into the contribution of the steps before κ(ω n ) and the ones after:

P (Λ ≥ x + t) ≤ P (k-1)∧κ(ωn) i=0 λ i ≥ x + P (κ(ω n ) ≥ k) + P κ-1 i=κ(ωn) λ i ≥ t . ( 12
)
For i ≥ κ(ω n ), Disc(Z i , q, R i ) is containe in δ(q, ω n ), the disk of radius ω n around q, and the contribution of the steps i

≥ κ(ω n ) is at most 2ω n |Φ ∩ δ(q, ω n )|. In particular P κ-1 i=κ(ωn) λ i ≥ t ≤ P 2ω n Po(πω 2 n ) ≥ t ≤ exp(-ω 3/2 n ),
for all n large enough provided that t ≥ 4πω 3 n . To make sure that the second contribution in ( 12) is also small, we rely on Proposition 8 and choose

k = L 0 /E[R(1+cos 2α)]+2ω 2 n √ 2L 0 +ω n so that P(κ(ω n ) ≥ k) ≤ 4 exp(-ω 3/2 n ).
Finally, to deal with the first term in [START_REF] Devillers | Walking in a triangulation[END_REF], we note that on G k , the random variables λ i , i = 0, . . . , k + 1 are independent given R i , i = 0, . . . , k + 1. Let R i , i = 0, . . . , k -1 be i.i.d. copies of R conditioned on R ≤ ω n /ξ; then let τi be independent given R i , i = 0, . . . , k + 1, and such that τi = Po((π-A) R i ); finally, let λi = 2R i (1+ τi ). We choose x = kE[ λ0 ]+y with y = √ L 0 ω 4 n . Using arguments similar to the ones we have used in the proofs of Propositions 8 and 10, we obtain

P (k-1)∧κ(ωn) i=0 λ i ≥ x ≤ P k-1 i=0 λi ≥ x + P(G c k ) (13)
≤ exp -y 2 2kV( λ0 ) + 2ω 2 n y/3

+ P ∃i < k : λi ≥ ω 2 n + P (G c k ) .
To bound the second term in the right-hand side above, observe that for i < k, we have, for any Inria x > 0,

P λi ≥ x 2 ≤ P (1 + τi )2 R i ≥ x 2 ≤ P (1 + τi )2R i ≥ x 2 2 R i ≤ x + P 2 R i ≥ x ≤ P 1 + τi ≥ x 2 R i ≤ x + P 2 R i ≥ x ≤ P Po((π -A)x 2 /4) ≥ x -1 + exp(-Ax 2 /4) ≤ 2 exp(-ηx 2 ),
for some constant η > 0 and all x large enough. It follows immediately that V( λ0 ) < ∞ and that, n large enough,

P ∃i < k : λi ≥ ω 2 n ≤ k exp(-ηω 2 n ) ≤ exp(-ω 3/2 n ). (14)
Going back to (13), we obtain

P (k-1)∧κ(ωn) i=0 λ i ≥ x ≤ 3 exp(-ω 3/2 n ),
since here, we can assume that L 0 ≥ ω n (if this is not the case, the points outside of the disc of radius ω n centered at q do not contribute). Putting the bounds together yields

P (Λ ≥ x + t) ≤ 8 exp(-ω 3/2 n ),
and the claim follows by observing that for

c := E[2(1 + Po((π -A)R 2 ))R] E[R(1 + cos 2α)] = 2E[R] + E[2(π -A)R 3 ] E[R(1 + cos 2α)] ,
it is the case that cL 0 + (3 √ L 0 + 1)ω 4 n ≥ x + t for all n large enough. Simple integration using the distributions of R and α then yields the expression in [START_REF] Devillers | The Delaunay hierarchy[END_REF].

Algorithmic complexity

The complexity of the algorithm CONE-WALK(z, q) (which we sometimes denote T for brevity) is not quite given by the number of sites visited by the walk. Indeed, the set of vertices accessed by the algorithm also includes all of the neighbours of the visited sites. We now show that counting these also results in a bound of order O( √ n ). This proof is more intricate since [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF] the regions in which the points lie at step i and j = i may not be disjoint, and (2) one point may be checked by the algorithm multiple times at different steps. We proceed as follows: first, for a given step i, we prove a tail bound on the radius of the region in which the points accessed by the algorithm must lie. This gives us a bound on N i , the number of sites accessed by the algorithm in step i. Therefore, according to Section 2.1, the algorithmic complexity of step i is

Q R v u π 4 Radius = Q -(Q + R) sin π 8
Figure 9: Bounding the number of neighbours for one step of the walk. THE REGION WHERE THE POINTS LIE. Consider an arbitrary step i. We will provide a deterministic construction which allows us to bound the distance to the furthest point that may be accessed by the algorithm during step i. Here, the distance is measured with respect to the centre of the disk Disc(Z i , q, R i ). All the points which are accessed by the algorithm are neighbours of some site inside Disc(Z i , q, R i ), and hence it suffices to bound the region in which those neighbours lie.

less than τ i N i ≤ N 2 i . We prove that κ-1 i=0 N 2 i is O( √ n ) in
To this aim, consider the 'flower-like' construction given in Figure 9. This construction is simply the intersection of eight equally-spaced circles of equal radius on the border of the disc Disc(Z i , q, R i ). We imagine growing the common radius x of the circles until each of the lenses defined by their intersections contains at least one site of Φ. At this point no Delaunay neighbour can lie outside of the outer-most circle by the empty-circumcircle property of the Delaunay triangulation. To simplify computations, we now focus on circles inscribed within these lenses. Clearly, when all these circles are non-empty, each one of the lenses is non-empty, and no neighbour lies outside of the outer-most circle. For

x ≥ R i sin(π/8) 1 -sin(π/8) ,
the radius of one small circle is x -(x + R i ) sin(π/8) ≥ 0. Let Q i denote the smallest value x such that all eight small circles contains at least one site from Φ and let B i denote the disk concentric with Disc(Z i , q, R i ) of radius R i + 2Q i (see Figure 9). Then Q i ≥ x only if at least one of the small circles which lies the domain is empty (here, some portion of B i might lie Inria outside D n ). Since there are at most eight of them, we have

P (Q i ≥ x | R i ) ≤ 8P Po(π(x -(x + R i ) sin(π/8)) 2 ) = 0 | R i = 8 exp(-π(x -(x + R i ) sin(π/8)) 2 ). (15)
Given Q i , all the Delaunay neighbours of some site in Disc(Z i , q, R i ) must lie in B i and

N i ≤ |B i ∩ Φ| ≤ 8 + Po(π(R i + 2Q i ) 2 -AR 2 i )
(the search cone is empty and we must count the eight points which we know lie inside the small circles). We also define define Q by

P(Q ≥ x) = E[8 exp(-π max{x -(x -R) sin(π/8), 0} 2 )].
BOUNDING THE SUM OF CONTRIBUTIONS OF STEPS. The complexity T is bounded as follows:

T ≤ κ-1 i=0 N 2 i . (16)
Unlike in the case of the previous parameters, there is no way to make the summands in ( 16) independent by conditioning on some natural event which should occur with high probability: the discs with radii R i + 2Q i will intersect! It would be rather easy to obtain a bound of O( √ n log n) using crude arguments, however we do not settle for this suboptimal result and aim at an O( √ n ) upper bound. We show the following:

Proposition 12. The complexity of the algorithm CONE-WALK(z, q), starting from a site z ∈ Φ with L 0 = zq , satisfies

P T ≥ c T L 0 + L 0 ω 8 n + ω 4 n ≤ 11 exp(-ω 3/2 n ) with c T = 8 + 17E[π(R + 2Q) 2 -AR 2 ] + E[(π(R + 2Q) 2 -AR 2 )) 2 ] E[R(1 + cos 2α)] .
To deal with the dependence in the sum, we rely on the result by Janson [START_REF] Janson | Large deviation for sums of partially dependent random variables[END_REF] in which the dependence is quantified using the chromatic number of a dependence graph [see also [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF]Chapter 3]. Given the number of steps κ, let G be the graph on {1, 2, . . . , κ -1} in which the edge {ij} is included if and only if N i and N j are dependent. In the present case, the graph G is random and we let χ(G) denote its chromatic number. Because of the depence in the N i , i = 0, . . . , κ -1, we need to be a little careful in bounding the sum. Consider the event

E c,k,b := χ(G) ≤ c and ∀i < κ, N 2 i ≤ b and κ ≤ k .
We use the result of [START_REF] Janson | Large deviation for sums of partially dependent random variables[END_REF] conditional on E c,k,b , for some values of c, k and b to be chosen later:

P κ-1 i=0 N 2 i -E[N 2 i | E c,k,b ] ≥ t E c,k,b ≤ exp -2 t 2 ckb 2 . ( 17
)
for all n large. For the indices i such that L i ≥ 2ω 4 n , we choose 1 = ω 3 n /3 so that L i ≥ (2 1 + 1)ω n and the conditions to use Lemma 7 are satisfied for 1 . Note also that for n large 1 E[R]/2 ≥ 10ω n . We now consider any ≥ 1 . We have,

P(i ∼ i + ) ≤ P (L i -L i+ ≤ R i + R i+ + 2(Q i + Q i+ )) ≤ P (L i -L i+ ≤ 10ω n ) + P (R i + R i+ + 2(Q i + Q i+ ) ≥ 10ω n ) ≤ P (L i -L i+ 1 ≤ 10ω n ) + P (R i + R i+ + 2(Q i + Q i+ ) ≥ 10ω n ) ,
by monotonicity of L i . By Lemma 7, it follows that, for all ≥ 1

P (i ∼ i + ) ≤ exp(-η 1 /ω n ) + exp(-ω 3/2 n ) ≤ 2 exp(-ω 3/2 n ). (22)
Collecting the results in ( 21) for i such that L i ≤ 2ω 4 n and ( 22) for L i ≤ 2ω 4 n , proves the claim.

Putting together the bounds in [START_REF] Mcdiarmid | Concentration[END_REF] and Lemma 13 we have just proved that, for the value of k in [START_REF] Matoušek | Lectures on discrete geometry[END_REF], c = 2ω 2 n and b = 81ω 4 n , we have for all n large

P(E c c,k,b ) ≤ 10 exp(-ω 3/2 n ). (23)
Proof of Proposition 12. It now suffices to deal with the bound of the actual complexity conditional on E c,k,b in ( 17), which requires bounding

E[N 2 i | E c,k,b ].
Observe that, by [START_REF] Preparata | Planar point location revisited[END_REF], and for n large enough,

E[N 2 i | E c,k,b ] ≤ E[N 2 i ](1 + 2P(E c c,k,b )).
Now R i is dominated by R and Q i is dominated by Q. Then, one easily verifies that this implies that for every i, N i is stochastically dominated by N = 8 + Po(π(R + 2Q) 2 -AR 2 ). It follows that, for κ ≤ k and n large enough, we have

κ-1 i=0 E[N 2 i | E c,k,b ] ≤ kE[N 2 ] + exp(-ω 3/2 n /2) ≤ L 0 E[N 2 ] E[R(1 + cos 2α)] + ω 3 n L 0 + ω 4 n . (24)
Finally, using [START_REF] Preparata | Computational Geometry: An Introduction[END_REF] and with c

T = E[N 2 ]/E[R(1 + cos 2α)], P T ≥ L 0 c T + ω 3 n L 0 + ω 4 n + t ≤ P κ-1 i=0 N 2 i -E[N 2 i | E c,k,b ] ≥ t E c,k,b + P(E c c,k,b ) ≤ exp - t 2 kω 25/2 n + 10 exp(-ω 3/2 n ) ≤ 11 exp(-ω 3/2 n ),
for all t ≥ √ kω 7 n . One can (slightly) simplify the expression for c T using the fact

E[N ] = E[(8 + Po(π(R + 2Q) 2 -AR 2 )) 2 ] = 8 + 17E[π(R + 2Q) 2 -AR 2 ] + E[(π(R + 2Q) 2 -AR 2 )) 2 ].
(Further computations are unnecessary since they would yield too complicated an expression.)

The claimed bound then then follows form observing that that k = O(L 0 ).

Relaxing the model and bounding the cost of the worst query

The analysis in Section 3 was provided given the assumption that q was the centre of a disc containing Φ for clarity of exposition. We now relax the assumptions on both the shape of the domain D and the location of the query q. Taking D to be a disc with q at its centre ensured that Disc(z, q, r) was included in D for r ≤ zq and thus the search cone and disc were always entirely contained in the domain D. If we now allow q to be close to the boundary, it may be that part of the search cone goes outside D.

To begin with, we leave D unchanged and allow q to be any point in D. Given any point z ∈ D, the convexity of D ensures that the line segment zq lies within D. Furthermore, one of the two halves of the disc of diameter zq is included within D. Thus for any z, q ∈ D and r ∈ R the portion of Cone(z, q, r) (resp. Disc(z, q, r)) within D has an area lower bounded by half of its actual area (including the portion outside D). Since the distributions of all of the random variables rely on estimations for the portions of area of Cone(z, q, r) or Disc(z, q, r) lying inside D, we have the same order of magnitude for κ, K, Λ and T , with only a degradation of the relevant constants. The proofs generalise easily, and we omit the details. (Note however, that upper and lower bounds in an equivalent of Proposition 8 would not match any longer.)

The essential property we used above is that a disc with a diameter within D has one of its halves within D. This is still satisfied for smooth convex domains D and for discs whose radius is smaller than the minimal radius of curvature of ∂D. Thus our analysis may be carried out provided all the cones and discs we consider are small enough. The conditioning on the event G k which we used in Section 3 precisely guarantees that for all n large enough, on G k , all the regions we consider are small enough (O(log n/ √ n ) = o(1) in this scaling), and that G k still occurs with high probability. These remarks yield the following result. As before, D n = √ nD denotes the scaling of D with area n. Thus we obtain upper tail bounds for the number of steps κ(z, q), the number of visited sites K(z, q), the length Λ(z, q) and the complexity T (z, q) which are uniform in the starting point z and the location of the query q. Such tail bounds allow us to strengthen the result and Inria to estimate the value of the parameters for the worst possible pair of starting point and query location, sup z∈Φ n ,q∈Dn Γ(z, q), for Γ ∈ {κ, K, Λ, T }. By Lemma 6, the number of possible walks in a given Delaunay tessellation of size n is at most n × n 4 . For any x > 0, we have for n large enough. This proves Theorem 1.

Comparison with Simulations

We implemented CONE-WALK in C++ using the CGAL libraries. For simulation purposes we generated a Poisson process of rate 1 in a box of side 2 × 10 3 (giving approximately 4 × 10 6 points). We then obtained the following results by averaging over 10 5 different walks, starting from random points in a box of side 200, centred at the origin with a uniformly random destination point. For comparison, we provide expected bounds given by a walk with a destination at infinity, see Table 1. To compute expectations for the path length we considered the worst case in which the path visited all of the sub-steps, thus we also provide the simulated values for these quantities in brackets.

Figure 1 :

 1 Figure 1: Choosing the next vertex.

Figure 2 :Figure 3 :

 23 Figure 2: Example of cone walk.

β π 8

 8

Figure 4 :

 4 Figure 4: For the proof of Lemma 4.

Figure 5 :Figure 6 :

 56 Figure 5: For the proof of Lemma 5.

Figure 8 :

 8 Figure 8: Computing distance progress at step i.

  probability and in expectation by quantifying precisely the dependence relationships between each step.

Proposition 14 .

 14 Let D be a fixed smooth convex domain of area 1 and diameter δ. Consider a Poisson point processΦ n z of intensity 1 contained in D n = √ nD. Let z, q ∈ D n . Let Φ n z be Φ n conditioned on z ∈ Φ n . Then, there exist constants C Γ,D , C Γ,D , Γ ∈ {κ, K, Λ, T } such thatfor the cone walk on Φ n z , and all n large enough, we have sup z,q∈Dn P Γ(z, q) > C Γ,D √ n ≤ A Γ,D exp(-ω 3/2 n ).

P

  sup z∈Φ n ,q∈Dn Γ(z, q) ≥ x = E P sup z∈Φ n ,q∈Dn Γ(z, q) ≥ x |Φ| ≤ E P sup z∈Φ n ,q∈Dn Γ(z, q) ≥ x |Φ| • 1 {|Φ n |≤2n} + P (|Φ n | > 2n) ≤ 32n 5 E sup z,q∈Dn P Γ(z, q) ≥ x |Φ n |, z ∈ Φ n 1 {|Φ n |≤2n} + P(Po(n) > 2n) ≤ 32n 5 sup z,q∈Dn P (Γ(z, q) ≥ x | z ∈ Φ n ) + exp(-n/3) ≤ A Γ,D exp(-ω 3/2 n /2)for all n large enough, by Proposition 14. This is first claim of Theorem 1. Furthermore, sinceκ, K ≤ |Φ n |, Λ ≤ δ √ n and T ≤ |Φ n | 3, the previous argument also yields,E sup z∈Φ n ,q∈Dn Γ(z, q) ≤ C Γ √ n + E max{δ √ n, |Φ| 3 } • 1 {sup z∈Φ n ,q∈Dn Γ(z,q)≥C Γ √ n} ≤ C Γ √ n + E[(δ √ n + |Φ n |) 6 ] • P sup z∈Φ n ,q∈Dn Γ(z, q) ≥ C Γ √ n ,byCauchy-Schwarz inequality. Since E[Po(n) 6 ] ≤ 2n 6 , for n large, it follows easily that E sup z∈Φ n ,q∈Dn Γ(z, q) ≤ 2C Γ √ n + 4n 3 exp(-ω 3/2 n /2) ≤ 3C Γ √ n,

Table 1 :

 1 Comparison of theory with simulations. Inequalities are used to show when values are bounds.

	Theory	Theory (5 s.f.)	Simulation

RR n°8194

Taking any pair of X 2 as start and query points yields a different walk, which gives the trivial quadratic lower bound.Inria

RR n°8194RESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgment. We would like to thank Marc Glisse, Mordecai Golin, Jean-François Marckert, and Andrea Sportiello for fruitful discussions during the Presage workshop on geometry and probability.

In order to prove the claim, it now remains to estimate P(E c c,k,b ) in order to choose the values of c, k and b, and then to relate E[N 2 i | E c,k,b ] to c T for these values. We start by bounding P(E c c,k,b ):

For the last term to be small, we choose

and we rely on Corollary 9. For this value of k, we obtain P(κ ≥ k) ≤ 5 exp(-ω

The second term is easily bounded using the bounds for R i in (2) and for Q i in [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF]. For all n large enough, we have

In particular, since ω n ≥ log n and k = O( √ n ), the union bound implies that, for all n large enough

Bounding the chromatic number is slightly more complex. Our aim is to choose c = 2ω 2 n . We prove the following lemma: Lemma 13. For all n large enough, we have

Proof. For simplicity, we bound χ(G) using the maximum degree ∆(G): we have χ(G) ≤ ∆ (G) := ∆(G) + 1. Also, the edge {ij} may be included in G only if the regions B i and B j intersect; in that case, we write i ∼ j. The underlying idea is that if is large, then the sites Z i and Z i+ should be too far apart for the regions B i and B i+ to intersect with a decent probability. So we prove that there exists 0 large enough such that, with high probability, there exists no edge {i, i + } with ≥ 0 , hence that ∆ (G) ≤ 2 0 + 1.

Consider the indices i such that L i ≤ 2ω 4 n . The number of edges of the form i ∼ i + is at most the number of steps of the walk started from Z i . By Proposition 8, and since E[R(1 + cos 2α)] > 1, we have for such values of i,

Inria