Pedro Machado

Manhães De Castro

Olivier Devillers
email: olivier.devillers@inria.fr

Practical Distribution-Sensitive Point Location in Triangulations *

We design, analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical Jump & Walk, called Keep, Jump, & Walk. For a batch of query points, the main idea is to use previous queries to improve the current one. In practice, Keep, Jump, & Walk is actually a very competitive method to locate points in a triangulation. We also study some constantmemory distribution-sensitive point location algorithms, which work well in practice with the classical space-filling heuristic for fast point location. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log #(pq)) randomized expected complexity, where p is a previously located query and #(s) indicates the number of simplices crossed by the line segment s. The Delaunay hierarchy has O(n log n) time complexity and O(n) memory complexity in the plane, and under certain realistic hypotheses these complexities generalize to any finite dimension. Finally, we combine the good distribution-sensitive behavior of Keep, Jump, & Walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called Keep, Jump, & Climb. To the best of our knowledge, Keep, Jump, & Climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations.

Introduction

Point location in spatial subdivision is one of the most classical problems in computational geometry [START_REF] Goodman | Handbook of Discrete and Computational Geometry[END_REF]. Given a query-point q and a partition of the d-dimensional space in regions, the problem is to retrieve the region containing q. This paper addresses the special case where the spatial subdivision is a simplicial complex, also called triangulation.

In two dimensions, locating a point has been solved in optimal O(n) space and O(log n) worst-case query time a quarter of a century ago by Kirkpatrick's hierarchy [START_REF] Kirkpatrick | Optimal search in planar subdivisions[END_REF]. In three dimensions, optimal point location remains an open problem [START_REF] Demaine | The Open Problems Project[END_REF]. While O(log n) is the best worst-case query time one can guarantee, it turns out that it is possible to improve the query time when successive queries have some spatial coherence. For instance, spatial coherence occurs (i) when the queries follow some specific path inside a region, (ii) when a method (e.g., the Poisson surface reconstruction [START_REF] Kazhdan | Poisson surface reconstruction[END_REF][START_REF]CGAL User and Reference Manual[END_REF]) uses point dichotomy to find the solution to some equation, or (iii) in geographic information systems, where the data base contains some huge geographic area, while the queries lie in some small region of interest. During the last twenty-five years, computer geometers borrowed from the classical one-dimensional framework [START_REF] Knuth | Optimum binary search trees[END_REF][START_REF] Iacono | Improved upper bounds for pairing heaps[END_REF], two ways to take the spatial coherence into account in point location algorithms: (i) using the entropy of the query distribution [START_REF] Arya | A simple entropy-based algorithm for planar point location[END_REF][START_REF] Iacono | Expected asymptotically optimal planar point location[END_REF], and (ii) designing algorithms that have a self-adapting capability, i.e. algorithms that are distribution-sensitive [START_REF] Iacono | Proximate planar point location[END_REF][START_REF] Demaine | Proximate point searching[END_REF].

Entropy. Entropy-based point location assumes that a distribution on the set of queries is known. There are some well-known entropy-based point location data structures in two dimensions. Arya et al. [START_REF] Arya | A simple entropy-based algorithm for planar point location[END_REF] or Iacono [START_REF] Iacono | Expected asymptotically optimal planar point location[END_REF], both achieve a query time proportional to the entropy of that distribution, linear space, and O(n log n) preprocessing time. Those algorithms are asymptotically optimal [START_REF] Malamatos | Lower bounds for expected-case planar point location[END_REF]. However, in many applications the distribution is unknown. Moreover, the distribution of query points can deliberately change over time. Still, it is possible to have a better complexity than the worst-case optimal if queries are very close to each other.

Distribution-sensitiveness. A point location algorithm that adapts to the distribution of the query is called a distribution-sensitive point location algorithm. A few distribution-sensitive point location algorithms in the plane exist: Iacono and Langerman [START_REF] Iacono | Proximate planar point location[END_REF] and Demaine et al. [START_REF] Demaine | Proximate point searching[END_REF]. Both achieve a query time that is logarithmic in terms of the distance between two successive queries for some special distances. However the space required is above linear, and preprocessing time is above O(n log n). More recently, a 2D point location algorithm that theoretically behaves as good as the best entropy-based algorithms (in an amortized sense) without a priori knowledge of query distribution has been proposed by Iacono [START_REF] Iacono | A static optimality transformation with applications to planar point location[END_REF] in SoCG 2011.

Walk. Despite the good theoretical query time of the point location algorithms above, alternative algorithms using simpler data structures are still used by practitioners. Amongst these algorithms, walking from a simplex to another using the neighborhood relationships between simplices, is a straightforward algorithm which does not need any additional data structure besides the triangulation [START_REF] Devillers | Walking in a triangulation[END_REF]. Walking performs well in practice for Delaunay triangulations, but has a non-optimal complexity [START_REF] Devroye | Expected time analysis for Delaunay point location[END_REF].

Building on walk. Building on the simplicity of the walk, both the Jump & Walk [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF] and the Delaunay hierarchy [START_REF] Devillers | The Delaunay hierarchy[END_REF] improve the complexity while retaining the simplicity of the data structure. The main idea of these two structures is to find a good starting point for the walk in order to reduce the number of visited simplices [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF][START_REF] Carufel | Point location in well-shaped meshes using jump-and-walk[END_REF][START_REF] Devillers | The Delaunay hierarchy[END_REF][START_REF] Zhu | Adaptive point location with almost no preprocessing in Delaunay triangulations[END_REF]. In two dimensions, Jump & Walk guarantees randomized O( 3 √ n) query time for random Delaunay triangulations with no other preprocessing than the computation of the Delaunay triangulation 1 , whereas the Delaunay hierarchy guarantees a randomized O(log n) worst-case query time for any Delaunay triangulation, but with O(n log n) preprocessing. Furthermore, these methods based on walking extend well for any finite dimension, which is not true for the aforementioned optimal algorithms. Under some realistic hypotheses, the Delaunay hierarchy guarantees a randomized O(log n) worst-case query time even for Delaunay triangulations in the d-dimensional space [START_REF] Devillers | The Delaunay hierarchy[END_REF]. Delaunay hierarchy is currently implemented as the Fast location policy of the Computational Geometry Algorithms Library [START_REF]CGAL User and Reference Manual[END_REF][START_REF] Yvinec | 2D triangulations[END_REF][START_REF] Pion | 3D triangulations[END_REF] (Cgal).

Contribution. In this paper, we propose several new ideas to improve point location in practice. Under some hypotheses satisfied by "real point sets", we also obtain interesting theoretical analysis.

In Section 3, we introduce the Distribution Condition: A region C of a triangulation T satisfies this condition if the expected cost of walking in T along a segment inside C is in the worst case proportional to the length of this segment. In Section 7.1, we provide experimental evidence that some realistic triangulations satisfy the Distribution Condition for the whole region inside their convex hull. And, we relate this condition to the length of the edges of some spanning trees embedded in R d , to obtain complexity results. Section 3.1 reviews some of the most common forms of trees embedded in the space. We recall some interesting results concerning their lengths, which are useful in the sequel.

In Section 4, we investigate constant-size-memory strategies for choosing the starting point of a walk. More precisely, we compare strategies that are dependent on previous queries and strategies that are not, mainly in the case of random queries. Random queries are, a priori, not favorable to distribution-sensitive strategies, since there is no coherence between them. Nevertheless, our computations prove that distributionsensitive strategies are, either better, or not dramatically worse in this case. Thus, there is a good reason for the use of distribution-sensitive strategies, since they are competitive even in situations that are seemingly unfavorable. Section 7.2 provides experiments to confirm such behavior on realistic data.

In Section 5, we revisit Jump & Walk so as to make it distribution-sensitive. The modification is called Keep, Jump, & Walk. In a different setting, Haran and Halperin verified experimentally [START_REF] Haran | An experimental study of point location in planar arrangements in CGAL[END_REF] that similar ideas in the plane gives interesting running time in practice. Here, we give theoretical guarantees that, under some conditions, the expected amortized complexity of Keep, Jump, & Walk is the same as the expected complexity of the classical Jump & Walk. We also provide analysis for some modified versions of Keep, Jump, & Walk.

In Section 7.4, experiments show that Keep, Jump, & Walk, has an improved performance compared to the classical Jump & Walk in 3D as well. Despite its simplicity, it is a competitive method to locate points in a triangulation.

In Section 6, we show that climbing the Delaunay hierarchy can be used to answer a query q in O(log #(pq)) randomized expected complexity, where p is a point with a known location and #(s) indicates the expected number of simplices crossed by the line segment s. Climbing instead of walking makes Keep, Jump, & Walk become Keep, Jump, & Climb, which appears to take the best of all methods both in theory and in practice. 2 Walking in a Triangulation

Walking Strategies

First, let us define the visibility graph VG(T , q) of a triangulation T of n points in dimension d and a query point q. VG(T , q) (or simply VG when there is no ambiguity) is a directed graph (V, E), where V is the set of d-simplices of T , and a pair of simplices (σ i , σ j ) belongs to the set of edges E if σ i and σ j are adjacent in T and the supporting hyperplane of their common facet separates the interior of σ i from q; see Figure 1.

When two simplices σ i and σ j are such that (σ i , σ j ) ∈ E, we will say that σ j is a successor of σ i . Now, a visibility walk (also called Lawson's oriented walk) consists in repeatedly walking from a simplex σ i to one of its successor in VG until the simplex containing q is found; a walking strategy describes how this successor is chosen.

q The following two walking strategies will be considered: (i) the straight walk is a visibility walk where each visited simplex intersects the segment pq; and (ii) the stochastic walk is a visibility walk where the next visited simplex, from a simplex σ, is randomly chosen amongst the successors of σ in VG.

The straight walk has a worst-case complexity linear in the number of simplices [START_REF] Shewchuk | Stabbing Delaunay tetrahedralizations[END_REF]. If T is the Delaunay triangulation of points evenly distributed in some finite convex domain and s is not close to the domain boundary, the expected number of simplices stabbed by a segment s is O( s • n 1/d ), for d = 2 [START_REF] Devroye | Expected time analysis for Delaunay point location[END_REF][START_REF] Bose | On the stabbing number of a random Delaunay triangulation[END_REF], for d = 3 [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF], and believed to be true for any d [START_REF] Green | Computing Dirichlet tessellations in the plane[END_REF][START_REF] Bowyer | Computing Dirichlet tesselations[END_REF]. Current results on the complexity of the stochastic walk are weaker: It is known that the stochastic walk finishes with probability 1 [START_REF] Devillers | Walking in a triangulation[END_REF], though it may visit an exponential number of simplices (even in R 2 ). In the case of Delaunay triangulations, the complexity improves to become linear in the number of simplices. For stochastic walk on Delaunay triangulations of evenly distributed points, we have the following conjecture.

Conjecture 1. If T is the Delaunay triangulation of points evenly distributed in some finite convex domain C and s a segment inside C, then the number of simplices visited during the stochastic walk is in O(1+ s •n 1/d ).

In practice, stochastic walk answers point location queries faster than the straight walk [START_REF] Devillers | Walking in a triangulation[END_REF] and it is the current choice of Cgal for the walking strategy [START_REF] Yvinec | 2D triangulations[END_REF][START_REF] Pion | 3D triangulations[END_REF], in both dimensions 2 and 3.

In this paper, our theoretical results work for any walking procedure such that the number of simplices visited during the walk is in O(1+ s •n 1/d ). As mentioned, this is verified for the straight walk in dimensions d = 2, 3, and conjectured for the straight and stochastic walk in any dimension. It has been empirically verified in [START_REF] Devillers | Walking in a triangulation[END_REF] that the stochastic walk is faster than the straight walk, easier to implement, and more robust to numerical errors. Henceforth, we use the stochastic walk for experiments (Section 7).

Orientation Predicate and its Exact Evaluation

Given two adjacent simplices, deciding which one is a successor of the other relies on the so-called orientation predicate: Given d + 1 points

p 0 = (x 0 0 , . . . , x 0 d-1 ), . . . , p d = (x d 0 , . . . , x d d-1
), the orientation predicate is defined as the sign of the following determinant.

x d 0 . . . x d d-1 1 ∈ {-1, 0, +1}. (1)
The polynomial induced by the determinant, from which we extract the sign for a given input, is called the predicate polynomial.

It is commonly assumed that the representation of a simplex σ of T gives its vertices p 0 , . . . , p d in an order corresponding to positive orientation orient(p 0 , p 1 , . . . , p d ) = +1.

Then, an adjacent simplex σ is the successor of σ if the supporting hyperplane of their common facet (say the facet containing p 1 , . . . , p d ) separates p 0 and q, which is true if orient(q, p 1 , . . . , p d ) = -1.

It is well known that, as for many computational geometry algorithms, an implementation of the predicate with floating point arithmetic may yield to robustness issues [START_REF] Kettner | Classroom examples of robustness problems in geometric computations[END_REF]; concerning the walk, the problem is that it may never terminate. The exact geometric computation paradigm [START_REF] Yap | The exact computation paradigm[END_REF] provides one interesting solution: evaluating the predicate exactly. However, since an exact evaluation of the predicate polynomial is quite expensive the trick is to have a filtered evaluation that is an approximate evaluation of the predicate polynomial with a certification of the exactness of its sign. If the certification is successful, the predicate is reasonably cheap. Otherwise, the expensive exact computation is called, but it does not arise often.

In the context of Cgal the approximate evaluation consists in computing the predicate polynomial with usual floating point arithmetic to produce a result δ. The certification computes a bound β on the maximal error between the inexact computation and the exact value, if |δ| > β, then the inexact computation is certified, and we are done; otherwise, an exact computation using multi-precision type [START_REF]Core number library[END_REF][START_REF] Devillers | Library for efficient data types and algorithms[END_REF][START_REF]The Gnu multiple precision arithmetic library[END_REF] is performed.

Optimizing through Structural Filtering

As mentioned, the exactness of the walk is certified by exact computations, which are classically accelerated with arithmetic filtering. To speed-up the walking procedure even more, we can use a filtering scheme called structural filtering, proposed by Funke et al. [START_REF] Funke | Structural filtering: A paradigm for efficient and exact geometric programs[END_REF], which works at a higher level than the classical arithmetic filtering scheme. It is based on the relaxation of the exactness of the predicates.

More precisely, the correctness of the visibility walk relies on the exactness of the orientation predicates. The filtering mechanism accelerates the exact computation of the orientation predicate (see Section 2.2), but it remains slower than a direct evaluation with floating-point numbers without any certification of the sign at all. Structural filtering extends this classical filtering mechanism to a higher level. Instead of certifying exactness at each orientation predicate, the process just certifies that the returned simplex contains the query. Since a walk is mostly dependent on the performance of the orientation predicate, using a cheaper predicate will improve the whole performance of the walk. Therefore, a two-phases exact algorithm can be designed:

• The first phase consists in running the visibility walk algorithm with an uncertified orientation predicate; we call this phase the relaxation phase. This phase either terminates in some simplex and returns that simplex, or visits a number of simplices above some threshold and then returns the current simplex. This threshold mechanism avoids a possible non-termination of the relaxation phase that rounding errors may produce in pathological situations. In any case, this phase returns a simplex (hopefully) not too far from the solution.

• The second phase consists in running the visibility walk algorithm with a certified orientation predicate starting at the simplex returned by the relaxation phase, until the solution is found; we call this phase the certification phase. If the first phase returned the correct simplex, which is the most common case, this phase just check that simplex is the right one.

Structural filtering accelerates around 20% the point location procedure; therefore, we adopt this scheme for experiments presented in this paper. (We have implemented structural filtering in Cgal 3.8.)

Distribution Condition

To analyze the complexity of the straight walk and derived strategies for point location, we need some hypotheses claiming that the behavior of a walk in a given region C of the triangulation is as follows.

Distribution Condition: Let ∆ be a triangulation scheme (such as Delaunay, Regular, . . .), let ρ be a distribution of points with compact support Σ ⊂ R d , and let C be a region inside Σ. For a triangulation T of n points following distribution ρ and built upon the triangulation scheme ∆, the Distribution Condition is satisfied if there exists a function F : N → R, such that for a segment s ⊆ C, the expected number of simplices of T intersected by s, averaging on the choice of the sites in the distribution, is less than.

One known case where the Distribution Condition is satisfied is the Delaunay triangulations of points following the Poisson distribution in dimension d = 2 [START_REF] Devroye | Expected time analysis for Delaunay point location[END_REF][START_REF] Bose | On the stabbing number of a random Delaunay triangulation[END_REF] and d = 3 [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF], where F(n) = O(n 1/d ), for any region C; see Figure 2(a). We believe that the distribution condition generalizes to other kinds of triangulation schemes and other kinds of distributions. An interesting case seems to be the Delaunay triangulation of points lying on some manifold in a space of dimension d ; see Figure 2(b)). The following conjecture is supported by our experiments (Section 7.1).

Conjecture 2. The Delaunay triangulations in dimension d of n points evenly distributed on a bounded manifold Π of dimension δ, satisfy the Distribution Condition inside the convex hull of Π, with

F(n) = O(n 1/δ ).
The Distribution Condition affects the relationship between the cost of locating points and the proximity between points. Let T be a triangulation of n points following some distribution with compact support

C T (a) C C (b) Figure 2: Distribution Condition. (a) F(n) = O( √ n), (b) F(n) = O(n).
in R d , if the distribution condition is satisfied for a region C in the convex hull of T , the expected cost of locating in T a finite sequence S of m query points lying in C by straight walk is at most

F(n) • m-1 i=1 |e i | + m, (2)
where e i is the line segment formed by the i-th starting point of the walk and the i-th query-point. The structure formed by all these segments has a special meaning for point location purpose. We shall see this meaning in what follows.

Let S = {q 1 , q 2 , . . . , q m } be a sequence of queries. For a new query, the walk has to start from a point whose location is already known, i.e. a point inside a simplex visited during a previous walk. Thus the line segments e i , 1 ≤ i ≤ m -1, formed by (i) the starting point of the i-th walk toward q i , and (ii) q i itself, must be connected. Therefore, the graph E formed by these line segments e i is a tree spanning the query points; we call such a tree the Location Tree. Its length is given by E = e∈E e . Eq.( 2) can be rewritten as the following expression:

F(n) • E + m. (3)
In the next section, we review some classical trees embedded in the space and the growth rate of their length.

On Trees Embedded in R d

The tree theory is older than computational geometry itself. Here, we mention some of the well-known trees (and graphs) [START_REF] Skiena | The Algorithm Design Manual[END_REF], which are related with the theory of point location. Let S = {p i , 1 ≤ i ≤ n} be a set of points in R d and G = (V, E) be the complete graph such that the vertex v i ∈ V is embedded on the point p i ∈ S; the edge e ij ∈ E linking two vertices v i and v j is weighted by its Euclidean length p ip j . G is usually referred to as the geometric graph of S.

We review below some well-known trees. Two special kinds of tree get a special name: (i) a star is a tree having one vertex that is linked to all others; and (ii) a path is a tree having all vertices of degree 2 but two with degree 1. EMST. Among all the trees spanning S, a tree with the minimal length is called an Euclidean minimum spanning tree of S and denoted EM ST (S); see Figure 3(a). EM ST can be computed with a greedy algorithm at a polynomial complexity.

EM ST (S) ≤ EM LP (S) < ET ST (S) < 2 EM ST (S) (4)
EMIT. Above, subgraphs of G are independent of any ordering of the vertices. Now, consider that an ordering is given by a permutation σ, vertices are inserted in the order v σ(1) , v σ(2) , . . . , v σ(n) . We build incrementally a spanning tree T i for S i = {p σ(j) ∈ S, i ≤ j} with T 1 = {v σ(1) }, T i = T i-1 ∪ {v σ(i) v σ(j) } and a fixed k, with 1 ≤ k < n, such that v σ(i) v σ(j) has the shortest length for any max (1, ik) ≤ j < i. This tree is called the Euclidean minimum k-insertion tree, and is denoted by EM IT k (S); see Figure 3(f). When k = n -1, we write EM IT (S); see Figure 3(c We present here some results on the length of the above-mentioned structures. We start by subgraphs independent of an ordering of the vertices. The Beardwood, Halton and Hammersley theorem [START_REF] Beardwood | The shortest path through many points[END_REF] states that if p i are i.i.d. random variables with compact support, then ET ST (S) = O(m 1-1/d ) with probability 1; by Eq.( 4) the same bound is obtained for both EM LP (S) and EM ST (S) . While this result gives a practical bound on the complexity, they are dependent on probabilistic hypotheses; this was shown to be unnecessary. Steele and Snyder prove [START_REF] Steele | Worst-case growth rates of some classical problems of combinatorial optimization[END_REF] that the complexity of these graphs remains bounded by O(m 1-1/d ) even in the worst case.

Consider the length of the path formed by sequentially visiting each vertex in V . This gives a total length of m i=2 p i-1 p i . Let V σ = {p σ(1) , p σ(2) , . . . , p σ(m) } be a sequence of m points made by reordering V with a permutation function σ such that points in V σ would appear in sequence on some space-filling curve. Platzman and Bartholdi [START_REF] Platzman | III. Spacefilling curves and the planar travelling salesman problem[END_REF] proved that in two dimensions the length of the path made by visiting S σ sequentially is a O(log m) approximation of ET ST (S) , and hence

m i=2 p σ(i-1) p σ(i) = O( √ m log m).
One of the main interests of such heuristic is that σ can be found in O(m log m) time.

Finally, Steele shows that the growth rate of EM IT (S) is as large as the one of EM ST (S) [START_REF] Steele | Cost of sequential connection for points in space[END_REF] (this result has been recently generalized [START_REF] De Castro | On the asymptotic growth rate of some spanning trees embedded in R d[END_REF]). More precisely: Theorem 3 (Steele [START_REF] Steele | Cost of sequential connection for points in space[END_REF]). Let S be a sequence of m points in [0, 1] d , d ≥ 2, then we have the following inequality:

|EM ST (S)| ≤ |EM IT (S)| ≤ γ d m 1-1/d . Here, γ d = 1 + 2 4d d d/2 /(d -1) is a constant depending only on d.

Constant-Size-Memory Strategies

In this section, we analyze the length of the Location Tree of strategies that store a constant number of possible starting points for a straight walk; this is naturally followed by a comparative study between them. Proofs of Theorems 4, 5, and 11 below are restricted cases of theorems proved in a companion paper [START_REF] De Castro | On the asymptotic growth rate of some spanning trees embedded in R d[END_REF].

Fixed-point strategy.

In the fixed-point strategy, the same point c is used as starting point for all the queries, then the Location Tree is the star rooted at c, denoted by S c (S). The best Location Tree we can imagine is the Steiner star, but of course computing it is not an option, neither in a dynamic setting nor in a static setting. This strategy is used in practice: In Cgal 3.6, the default starting point for a walk is the so-called vertex at infinity; thus the walk starts somewhere on the convex hull, which looks like a kind of worst strategy.

In the worst case, one can easily find a set of query-points S such that |ESS(S)| = Ω(m), or such that |S c (S)|/|ESS(S)| goes to infinity for some c. Now we focus on the case of evenly distributed queries. Theorem 4 ( [START_REF] De Castro | On the asymptotic growth rate of some spanning trees embedded in R d[END_REF], for α = 1). Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the expected length of the Location Tree of the best fixed-point strategy is

d d + 1 • m.
Theorem 5 ([13], for α = 1). Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the expected length of the Location Tree of the worst (on the choice of c inside the ball) fixed-point strategy is

2 d+1 2d + 1 2d + 2 B d 2 + 1 2 , d 2 + 1 B d 2 + 1 2 , 1 2 • m, where B(x, y) = 1 0 λ x-1 (1 -λ) y-1
dλ is the so-called Beta function. Corollary 6. Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the ratio between the expected lengths of the Location Tree of the best and worst fixed-point strategies is at most 2 (for d = 1), and at least √ 2 (when d → ∞).

Figure 4 gives the expected average length of an edge of the best and worst fixed-point Location Trees.

Last-point strategy.

An alternative to the fixed-point strategy is the last-point strategy. To locate a new query-point, the walk starts from the previously located query. The Location Tree obtained with such a strategy is a path. When T satisfies the Distribution Condition, the optimal path is the EM LP (S).

In the worst case, the length of such a path is clearly Ω(m); a straightforward example is to repeat alternatively the two same queries. In contrast with the fixed-point strategy, the last-point strategy depends on the query distribution. If the queries have some spatial coherence, it is clear that we improve on the fixed-point strategy. Such a coherence may come from the application, or by reordering the queries. There is always a permutation of indices on S such that the total length of the path is sub-linear [START_REF] Steele | Worst-case growth rates of some classical problems of combinatorial optimization[END_REF][START_REF] Gao | General spacefilling curve heuristics and limit theory for the traveling salesman problem[END_REF]. Furthermore, in two dimensions, one could find such permutation in O(m log m) time complexity [START_REF] Platzman | III. Spacefilling curves and the planar travelling salesman problem[END_REF].

Now, the question we address is "if there is no spatial coherence, how the fixed and last point strategies do compare?".

Theorem 7. The ratio between the lengths of the Location Tree of the last-point strategy and the fixed-point strategy is at most 2.

Proof. This is an easy consequence of the triangle inequality. Take S = p 1 , . . . , p m , and any fixed-point c. Then we have:

|p i p i+1 | ≤ |cp i | + |cp i+1 |,
for all 1 ≤ i < m. Summing the term above for each value of i leads to the inequality:

m-1 i=1 |p i p i+1 | ≤ m-1 i=1 |cp i | + m i=2 |cp i | ≤ 2 m i=1 |cp i |,
which completes the proof. Combining the results in Theorem 7 and Theorem 8, it is reasonable to conclude that the last-point strategy is better in general, as the improvement the fixed-point strategy could bring does not pay the price of its worst-case behavior. We now study the case of evenly distributed queries.

Theorem 9. Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the expected length of the Location Tree of the last-point strategy is

2 d+1 d d + 1 B d 2 + 1 2 , d 2 + 1 B d 2 + 1 2 , 1 2 • m.
Proof. This is equivalent to find the expected length of a random segment determined by two points uniformly independent and identically distributed in the unit ball, which is given in [START_REF] Santaló | Integral Geometry and Geometric Probability[END_REF].

Theorems 4, 5, and 9 give the following result:

Corollary 10. Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the ratio between the expected lengths of the Location Tree of the last-point and the best fixed-point strategies is at most √ 2 (when d → ∞), and at least 4/3 (when d = 1) whereas the ratio between the expected lengths of the Location Tree of the last-point and the worst fixed-point strategies is 2d/(2d + 1).

As shown in Figure 4, the last-point strategy is in between the best and worst fixed-point strategies, but closer and closer to the worst one when d increases. Thus, in the context of evenly distributed points in a ball, the last-point strategy cannot be worse than any fixed point strategy by more than a factor of √ 2. Still, the fixed-point strategy may have some interests under some conditions: (i) queries are known a priori to be random and; (ii) a reasonable approximation of the center of ESS(S) can be found.

k-last-points strategy.

We explore here a variation of the last-point strategy. Instead of remembering the place where the last query was located, we store the places where the k last queries were located, for some small constant k. These k places are called landmarks in what follows. Then to process a new query, the closest landmark are determined by O(k) brute-force comparisons, then a walk is performed from there. This strategy has some similarity with Jump & Walk, the main differences are that the sample has fixed size and depends on the query distribution (it is dynamically modified).

The Location Tree associated with such a strategy is EM IT k . It has bounded degree k + 1 (or the kissing number in dimension d, if it is smaller than k + 1) and its length is greater than EM ST and smaller than the length of the path associated to the same vertices ordering, thus previous results provide upper and lower bounds. A tree of length Ω(m/k) = Ω(m) is easily achieved by repeating a sequence of k queries along a circle of length 1. The following Theorem gives the complexity when the queries are evenly distributed: Theorem 11 ( [START_REF] De Castro | On the asymptotic growth rate of some spanning trees embedded in R d[END_REF], for α = 1). Let S be a sequence of m query-points uniformly independent and identically distributed in the unit ball, then the expected length of the Location Tree of the k-last-points strategy satisfies

1 d B k + 1, 1 d • m ≤ E(length) ≤ 2 1 d B k + 1, 1 d • m. (5)
Remark. Note that the constant γ d in Theorem 3 looks big. But it is indeed too pessimistic. Theorem 11 leads to Theorem 12, which gives a better constant for queries evenly distributed inside the unit sphere.

Theorem 12. Let S be a sequence of k query-points uniformly independent and identically distributed in the unit ball, then the expected value of EM IT (S) is 2

• Γ(1 + 1/d) • k 1-1/d as k → ∞ , where Γ(x) = ∞ 0 t x-1 e -t
dt is the Gamma function. Proof. From Theorem 11, we have that the expected length l i of the i-th edge of EM IT (S) in the unit ball for evenly distributed points, is such that

l i ≤ 2 d B i + 1, 1 d . Where B(x, y) = 1 0 λ x-1 (1 -λ) y-1
dλ is the Beta function. Summing the expression above for k -1 edges, and using the Stirling's identity B(x, y) ∼ Γ(y)x -y , we have that there exists k 0 < ∞, such that for k > k 0 , EM IT (S) is bounded by

(1 + ) • 2 • Γ(1 + 1/d) • k 1-1/d
with as small as we want.

Intuitively, if the queries have some not too strong spatial coherence, the k-last-points strategy seems a good way to improve the last-point strategy. Surprisingly, experiments in Section 7 shows that even if the points have some strong coherence, a small k strictly greater than 1 improves on the last-point strategy when points are sorted along a space-filling curve. More precisely, k = 6 improves the location time by up to 30% on some data sets. Experiments were done using the stochastic walk.

Keep, Jump & Walk

Preliminaries: Jump & Walk

The Jump & Walk strategy takes a random sample of k vertices (the dots in Figure 5) of T , and uses a two-steps location process in order to locate a query q. First, the jump step determines the nearest vertex in the sample in (brute-force) O(k) time, then a walk in T is performed from that vertex. In the classical analysis of Jump & Walk, it is assumed that T is the Delaunay triangulation of points evenly distributed; taking k = n 1/(d+1) gives a complexity of O(n 1/(d+1) ) [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF][START_REF] Devroye | A note on point location in Delaunay triangulations of random points[END_REF].

A distribution-sensitive modification: Keep, Jump, & Walk

As mentioned before, the Jump & Walk strategy [START_REF] Mücke | Fast randomized point location without preprocessing in two-and threedimensional Delaunay triangulations[END_REF][START_REF] Devroye | A note on point location in Delaunay triangulations of random points[END_REF] uses a set of k landmarks randomly chosen amongst the vertices of T , then a query is located by walking from the closest landmark. In order to ensure adaptation to the query distribution, instead of using vertices of T as landmarks, we keep previous queries as landmarks. Then, we have several possibilities: (i) we can use k queries chosen at random in previous queries, (ii) we can use the k last queries for the set of landmarks, and (iii) we can keep all the queries as landmarks, and regularly clear the landmarks set after a batch of k queries For any rule to construct the set of landmarks, the time to process a query q splits in: -Keep: the time K(k) for updating the set of landmarks if needed, -Jump: the time J(k) for finding the closest landmark l q , and -Walk: the time W (k) to walk from l q to q.

This modification performs surprisingly well in practice, experimental results for method (ii) are provided in Section 7. [START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF].

We analyze in this section the Keep, Jump, & Walk strategy considering the straight walk as the walk strategy. We start with the following lemma, which is a fundamental piece in this section.

Lemma 13. Let T be a triangulation of n points following some distribution with compact support in R d , if the Distribution Condition is satisfied for a region C in the convex hull of T , then W (k) has an expected amortized O F(n) • k -1/d + 1 complexity for k queries.

Proof. For k queries, the Location Tree of each variation above is an EM IT with k vertices. Let T be a triangulation of n points following some distribution with compact support in R d , if the Distribution Condition is satisfied for a region C in the convex hull of T , the expected cost of locating in T a finite

Climbing Up in the Delaunay Hierarchy

In this section, we show how the Delaunay hierarchy can be made distribution-sensitive under some hypotheses. Assume T is a Delaunay triangulation, then classical use of the Delaunay hierarchy provides a logarithmic cost in the total size of T to locate a point. The cost we reach here is logarithmic in the number of vertices of T in between the starting point and the query.

Given a set of n points P in the space, we assume that the expected size of the Delaunay triangulation of a random sample of size r of P has linear size. The hypothesis always holds in 2D, and is proved in several other situations: points randomly distributed in space [START_REF] Dwyer | Convex hulls of samples from spherically symmetric distributions[END_REF] or on a hypersurface [START_REF] Golin | On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes[END_REF][START_REF] Attali | A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces[END_REF][START_REF] Attali | Complexity of the Delaunay triangulation of points on surfaces: The smooth case[END_REF][START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF]. The Delaunay hierarchy [START_REF] Devillers | The Delaunay hierarchy[END_REF] constructs random samples P = P 0 ⊇ P 1 ⊇ P 2 ⊇ . . . ⊇ P h such that P rob(p ∈ P i+1 | p ∈ P i ) = 1/α for some constant α > 1. The h + 1 Delaunay triangulations D i of P i are computed and the hierarchy is used to find the nearest neighbor of a query q by walking at one level i from the nearest neighbor of q at the level i + 1. It is proven that the expected cost of walking at one level is O(α) and since the expected number of levels is log α n, we obtain a logarithmic expected time to descend the hierarchy for point location.

v 0 D 1 D 0 D 2 v 2 q v 1 q q Figure 6: Climbing.
a good starting vertex v = v 0 in D 0 is known, the Delaunay hierarchy can be used in another way: From v 0 a walk starts in D 0 visiting simplices crossed by segment v 0 q; the walk is stopped, either if the simplex containing q is found, or if a simplex having a vertex v 1 belonging to the sample P 1 is found. If the walk stops because v 1 is found, then a new walk in D 1 starts at v 1 along segment v 1 q. This process continues recursively up to the level l, where a simplex of D l that contains q is found; see Figure 6. Finally, the hierarchy is descended as in the usual point location. Theorem 14 bounds the complexity of this procedure. Theorem 14. Given a set of n points P, and a convex region C ⊆ CH(P), such that the Delaunay triangulation of a random sample of size r of P (i) has expected size O(r), (ii) satisfies the Distribution Condition in C with F(r) = O(r β ) for some constant β, then the expected cost of climbing and descending the Delaunay hierarchy from a vertex v to a query point q, both lying in C, is O(log w), where w is the expected cost of the walk from v to q in D the Delaunay triangulation of P.

Proof. Climbing one level. Since the probability that any vertex of D i belongs to D i+1 is 1/α, and that each time a new simplex is visited during the walk a new vertex is discovered, the expected number of visited simplices before the detection of a vertex that belongs to

D i+1 is at most 1 + ∞ j=0 j 1 α 1 -1 α j = α.
Descending one level. The cost of descending one level is O(α) [START_REF] Devillers | The Delaunay hierarchy[END_REF]Lemma 4]. Number of levels. Let w i denote the number of edges crossed by v i q in D i ; the Distribution Condition gives

w i = F(n/α i ) v i q ≤ F(n/α i ) v 0 q . If F(r) is a polynomial function O(r β )
, the expected number of levels that we climb before descending is less than l = (log w 0 )/β, since we have

w l = F(n/α l ) v l q ≤ F(n/α l ) v 0 q ≤ w 0 /α lβ = w 0 /α log w0 = 1
(where the big O have been omitted). Then, at level l the walk takes constant time.

Remind that in Section 5, we keep landmarks in order to improve the classical walking algorithm, which leads to Keep, Jump, & Walk. Now, it is natural to improve the climbing algorithm described above by adding landmarks in D 0 as well, and starting the climbing procedure from a good landmark. Since the complexity of climbing is O(log w), to balance the different costs, the number of considered landmarks has also to be O(log w). Using the hypotheses in Theorem 14, this number is given by O(log w) = O(log(F(n) • pq + 1)) = O(log(n pq )); neither F(n) nor the constant in the big O need to be known to ensure such a complexity. This approach is evaluated experimentally in the next section. Experiments have been realized on synthetic and realistic models (scaled to fit in the unit cube). The scanned models used here: Galaad, Pooran's hand, and Toy Turtle are taken from the Aim@shape repository; see Figure 7. The hardware used for the experiments described in the sequel, is a MacBook Pro 3,1 equipped with an 2.6 GHz Intel Core 2 processor and 2 GB of RAM, Mac OS X version 10.5.7. The software uses Cgal 3.6 and is compiled with g++ 4.3.2 and options -O3 -DNDEBUG. All the triangulations in the experiments are Delaunay triangulations. Each experiment was repeated 30 times, and the average is taken. We remind the reader that the walking strategy used in the section is the stochastic walk.

Experimental Results

We consider data sets in 2D and 3D; they are described in Table 2. Files of different sizes, smaller than the original model are obtained by taking random samples of the main file with the desired number of points.

The Distribution Condition

Our first set of experiments is an experimental verification of the Distribution Condition. We compute the Delaunay triangulation of different inputs, either artificial or realistic, with several sizes; for realistic inputs we construct files of various sizes by taking random samples of the desired size.

Figure 8 shows the number of crossed tetrahedra in terms of the length of the walk, for various randomly chosen walks in the triangulation. A linear behavior with some dispersion is shown. Though, from this uniform square (2D) Points evenly distributed in the unit square. anisotropic square (2D)

Points distributed in a square with a ρ = x 2 density. ellipse (2D)

Points evenly distributed on an ellipse; the lengths of the ellipsoid axes are 1/2, and 1.

uniform cube (3D)

Points evenly distributed in the unit cube. anisotropic cube (3D)

Points distributed in a cube with a ρ = x 2 density. ellipsoid (3D)

Points evenly distributed on the surface of an ellipsoid; the lengths of the ellipsoid axes are 1/3, 2/3, and 1. cylinder (3D)

Points evenly distributed on the surface of a cylinder; height and diameter of the cylinder are unitary. Galaad, Pooran's hand, and Toy Turtle (3D) a 3D model of a physical object. experiment, the walks that deviates significantly from the average behavior are more likely to be faster than slower, which is a good news From Figure 8, the slope of lines best fitting these point clouds give an estimation of F(n) for a particular n (namely n = 2 20 ). By doing these computations for several n, we draw F(n) in terms of the triangulation size in Figure 9. If F(n) is clearly bounded by a polynomial on n, then curves in Figure 9 should lie below some line. Now, from the biggest slope of lines tangent to these different curves, we evaluate the exponent of n. The points sampled on an ellipsoid give F(n) ∼ n 0.52 , and on a closed cylinder give F(n) ∼ n 0.51 , which are not far from Conjecture 2 that claims F(n) = O(n 1/2 ). The points evenly distributed in a cube give F(n) ∼ n 0.31 , which is not far from F(n) = O(n 1/3 ). For the scanned models, the curves are a bit concave, with a slope always smaller than 0.5; the Conjecture 2 is also verified in these cases, since the Distribution Condition claims only an upper bound and not an exact value for the number of visited tetrahedra.

k-last-points Strategy

CGAL library [START_REF] Pion | 3D triangulations[END_REF] uses spatial sorting [START_REF] Delage | Spatial sorting[END_REF] to introduce a strong spatial coherence in a set of points. For several models, we locate 1M queries evenly distributed inside the model with the k-last-point strategy after a spatial sorting of the queries. Surprisingly, using a small k slightly improves on k = 1 which indicates that even with such a strong coherence, k-last-points strategy is relevant. Figure 10 shows the running times on various sets for different values of k, taking k = 6 always improves on k = 1 and in some cases by a substantial amount.

Fine-tuning Constants

Regarding Keep, Jump, & Walk strategy, in Section 5.2, we have seen that, in theory, assuming the Distribution Condition, the correct number of landmarks for random points on 2D curves and 3D should be O(n 2/3 ), and O(n 3/8 ) respectively, and not O(n 1/3 ) and O(n 1/4 ), as customary. In this section, we verify experimentally that our complexities are better estimates for uniformly random points distributed on curves and surfaces. For each input model, both 2D and 3D, we have performed Keep, Jump, & Walk in order to locate 1M queries evenly distributed inside their respective Delaunay triangulations. We varied the amount of landmarks from few hundreds to around three thousands of them, and the size of the Delaunay triangulation from around 600K to 1M vertices; some of the graphs are depicted in Figure 11(a). From these graphs, we have taken the best performances, in order to showcase how the best number of landmarks varies with the number of vertices in the triangulation. We plot a log-curve so the slope of the fitted lines represent the degree of the polynomials inside the Big-O. The result is depicted in Figure 11(b). We can see that, for our input models, O(n 2/3 ), and O(n 3/8 ) are indeed better estimates for the number of landmarks in 2D curves and 3D surfaces, than O(n 1/3 ), and O(n 1/4 ) respectively.

From Figure 11(a), we can see that the performance of Keep, Jump, & Walk is harmed when too few or too much landmarks are taken. However, clearly, the extent of that damage is the greatest when too few landmarks are chosen; this is because evaluating distances is faster than evaluating orientation tests. Taking that into consideration, for the rest of the experiments, we have chosen constants inside the Big-O as indicated in Table 3.

Beside the four cases in Table 3, we also consider a fifth case: Keep, Jump, & Walk with a constant number of one hundred landmarks. When it is known that input queries have great spatial coherence, there is no need for too much landmarks; we include the later so we can have an idea of how much can be gained in performance when there is a priori knowledge of the spatial coherence of the queries. Similar experiments have been done for the Climb strategy, varying the α constant, for 1M location queries in 1M -sized models. The results showed in Figure 12(a) suggests that α = 9 is a consistently good choice for the climb strategy. Contrast with the classical Delaunay hierarchy strategy, which uses α = 30 [START_REF] Devillers | The Delaunay hierarchy[END_REF] (the best constant for the uniform distribution). For the Keep, Jump, & Climb strategy, we also have varied the number of landmarks. As in the Keep, Jump, & Walk strategy, our experiments showed that too few landmarks can significantly harm the performance. However, there are no relevant gain or loss in performance by adding more landmarks than a few hundreds. In practice, we use a constant number of 500 landmarks for the Keep, Jump, & Climb strategy in both 2D and 3D, instead of the more complex procedure described at the end of Section 6; this number of landmarks behave well in practice for 1M -sized input models. Figure 12(b) shows that, in 2D, α = 9 remains a good choice for the Keep, Jump, & Climb strategy, however in 3D, α = 40 becomes considerably better for almost all input models; these are also our choices for experiments in Section 7.4.

Performances

Now, we compare the performance of various point location procedures in 3D: classical Jump & Walk (J&W), walk starting at the previous query (last-point), Keep, Jump, & Walk described in Section 5 (K&J&W), and its variant with fewer landmarks (few K&J&W) as mentioned in Section 7.3, descending the Delaunay hierarchy (classical [START_REF] Devillers | The Delaunay hierarchy[END_REF]), climbing the Delaunay Hierarchy (Climb), and Keep, Jump, & Climb (K&J&C) 2 . For this purpose we consider the following experiment scenarios.

Scenario I -This scenario is designed to show how the proximity of queries relates to the point location algorithms performance. Let M be an input model with 2 20 vertices inside the unit cube, we first define S i , the 2 i vertices of M closest to some chosen point p in the cube. We have chosen p so the radii of the smallest balls containing S i , for i = 15, . . . , 20, are not extremely discrepant. Point p is (1/10, 1/2, 1/2) for Pooran's hand model, (1/4, 1/4, 7/10) for Galaad model, (7/10, 3/10, 1/4) for Toy Turtle model, and finally (1/2, 1/2, 1/2) for uniform cube. When i is large (resp. small), points are distributed in a large (resp. small) region on M. Then, we form the sequence A i of 2 20 points by taking 2 20 random point inside the smallest ball containing S i ; the value i is called the sparsity of the set. Figure 13 shows the computation times for point location and different strategies in function of i.

Scenario II -This scenario is designed to show how the spatial coherence of queries relates with the point location algorithms performance. Imagine a scenario where N random walkers w 0 , w 1 , . . . w N -1 , are walking simultaneously with the same speed inside the unit cube containing M, and at each steps, queries are issued for each walker position. Each random walker starts at different positions and with different directions. One step consists of a displacement of length 0.01 for all walkers. We compute the time to complete all 2 20 queries generated by 1 to 20 random walkers in Figure 14, and 100 to 2000 random walkers in Figure 15. One single walker means a very strong spatial coherence. Conversely, several walkers mean a weaker spatial coherence; at 2000 walkers, the number of random walkers surpasses the number of landmarks for all strategies.

The walk strategy used in the experiments is the stochastic walk. To guarantee honest comparisons, we use the same stochastic walk implementation for all the experiments: the stochastic walk implemented in Cgal [START_REF] Yvinec | 2D triangulations[END_REF][START_REF] Pion | 3D triangulations[END_REF].

From Scenario I. Figure 13 shows the total running time for answering 2 20 queries. It can be observed that the Keep, Jump, & Walk strategy actually benefits from the proximity of the queries and is clearly better than Jump & Walk and even better than the Delaunay hierarchy for the realistic models. Keep, Jump, & Walk with few landmarks performs better than Keep, Jump, & Walk with a higher number of landmark for strong locality, which is not surprising as computing distances between a point and landmarks is not for free. However, its performance suffers a lot more when the sparsity reaches its maximum level. Naturally, climbing the hierarchy is slower than descending the hierarchy when there is no locality and improves with locality. Finally, Keep, Jump, & Climb combines all the advantages and appears as the best solution in practice for this experiment: For low sparsity, it performs twice faster than the Delaunay hierarchy; and for high sparsity, it is as good as the Delaunay hierarchy (sometime even considerably faster).

From Scenario II (Figure 14 and15). With a single walker, the spatial coherence is very strong and we expect a very good result for the last-point strategy since it highly benefits from previous location without any overhead for maintaining any structure of any kind. We also expect better results for the Climb strategy in that situation. This and a lot faster when there is spatial coherence. Moreover, Keep, Jump, & Climb is strictly better than Keep, Jump, & Walk in theory, and even better than the Delaunay hierarchy.

Conclusion

Our aim was to improve in practice the performance of point location in triangulation and we are mostly interested in • queries with spatial coherence • inside 3D triangulations • in the CGAL library. Before starting this work, our best data structure for this purpose was the Delaunay hierarchy, which was able to handle 1M queries in a 1M points triangulation in about 12 seconds for various scenarios. We have proposed Keep, Jump, & Climb, a new way of using the Delaunay hierarchy, which is not slower and often The last-point strategy is sometime too slow to appear in the figures.

significantly faster than the classical descent of the Delaunay hierarchy in our experiments. For a reasonable amount of spatial coherence of the queries, running time are improved by a factor 2. (In Figure 13, Figure 14, and, Figure 15 the running times vary from around 1s to around 11s depending on the query coherence; this should be contrasted with the classical Delaunay hierarchy, which achieves from around 5s to around 12s.) One of our main tool in the theoretical analysis of our work is the introduction of the Distribution Condition that relates the expected number of tetrahedra intersected by a line segment with its length. It allows to analyze algorithms in a more general context than Delaunay triangulation of evenly distributed points. For example, we can derive from our work that the best size of sample for Keep, Jump, & Walk, when the data points lie on a surface, is n 3/8 and not the usual n 1/4 . Furthermore, our experiments show that the Distribution Condition actually corresponds to some practical cases.

From a theoretical point of view, climbing the Delaunay hierarchy provides a solution to the problem of distribution-sensitive point location, which is much simpler and faster than previous data structures [START_REF] Iacono | Proximate planar point location[END_REF][START_REF] Demaine | Proximate point searching[END_REF][START_REF] Iacono | A static optimality transformation with applications to planar point location[END_REF], but requires some reasonable hypotheses on the point set.

Open problems

The Distribution Condition brings several questions for the computational geometers. The first question is the one raised in Conjecture 2: Question 15. Do the Delaunay triangulations of n points evenly distributed on a bounded δ-dimensional manifold embedded in the d-dimensional space behave similarly to points evenly distributed in the Euclidean space of dimension δ with respect to the Distribution Condition?

If Conjecture 2 has an affirmative answer, then walking on such triangulations does not depend on the ambient dimension, but only on the manifold dimension. As a final remark, we want to insist on the dichotomy between the straight and stochastic walk. The straight walk is used in theoretical analysis for simplicity and usage of previous results, while the visibility walk is used in practice since it is faster and easier to implement. Thus an interesting research direction is to get a better theoretical basis for the use of the stochastic walk. This leads us to our last question: Question 17. Does Conjecture 1 have an affirmative answer?

Figure 1 :

 1 Figure 1: Visibility graph. Arrows represent edges of VG.

3. 2

 2 On the Growth Rate of Trees in R d .

Theorem 8 .

 8 The ratio between the lengths of the Location Tree of the last-point strategy and the fixed-point strategy is arbitrarily small. Proof. Consider a set of m queries distributed on a circle in R d . If the queries are visited along the circle, the length of the location tree of the last-point strategy is O(1), while |ESS| = Ω(m).

Figure 4 :

 4 Figure 4: Average lengths. Average lengths of an edge of the last-point, best and worst fixed-point Location Trees. The domain C here is a d-dimensional ball, and the queries are evenly distributed in C.

  q

Figure 5 :

 5 Figure 5: Jump & Walk. The walk starts from the nearest landmark (represented by dots above) with respect to the query. Then it ends at the cell containing the query.

Figure 7 :

 7 Figure 7: Scanned models.

Figure 8 :

 8 Figure 8: Distribution condition. of crossed tetrahedra in terms of the length of the walk. The number of points sampled in each model here is 2 20 .

  s o id P o o ra n 's H a n d G a la a d a n is o tr o p ic c u b e log n Tu rtle c y ll in d e r

Figure 9 :

 9 Figure 9: F(n) for some interesting cases. If F(n) is n β , β is given by the slope of above "lines" .

Figure 10 :

 10 Figure 10: Static point location with space-filling heuristic plus last-k-points strategy.

Figure 11 :

 11 Figure 11: Estimates for the best number of landmarks in Keep, Jump, & Walk strategy. In the right figure, filled symbols represent the log-curve of some polynomial on n specially chosen for better depiction. curves (2D) #landmarks = 0.23 * n 2/3 volumes (2D) #landmarks = 20 * n 1/3 surfaces (3D) #landmarks = 10 * n 3/8 volumes (3D) #landmarks = 42 * n 1/4

Figure 12 :

 12 Figure 12: Estimates for the best constants in hierarchy based strategies. Performances with respect to the Climb strategy, and the Keep, Jump, & Climb strategy are depicted in (a) and (b) respectively. 2D experiments don't go beyond α = 30, and in (b) they are shown in grey.

Figure 13 :

 13 Figure 13: Results for scenario I (proximity of queries). Computation times of the various algorithms in function of the sparsity of the set of points: (a) Pooran's hand model; (b) Galaad model; (c) Toy Turtle model; and (d) uniform.

  is indeed what happens, but Keep, Jump, & Walk with few landmarks, and Keep, Jump, & Climb remain quite close. When the number of walkers increases, the performance of last-point catastrophically falls down. The other strategies remain quite good until the number of walkers becomes higher than the number of landmarks, Keep, Jump, & Walk being the more resilient, since it requires a huge amount of landmarks. When the number of walkers becomes higher than the number of landmarks, the performance of the strategies fall down, specially the performance of Keep, Jump, & Walk with less landmarks. Keep, Jump, & Walk, Keep, Jump, & Climb, and the Delaunay hierarchy remain comparable. Overall, Keep, Jump, & Climb is as good as the Delaunay hierarchy when there is no spatial coherence,

Figure 14 :

 14 Figure 14: Results for scenario II (coherence of queries). Computation times of the various algorithms in function of the number of parallel random walkers for: (a) Pooran's hand model; (b) Galaad model; (c) Toy Turtle model; and uniform. Less random walkers mean strong spatial coherence (a single walker pushes that to an extreme).

Figure 15 :

 15 Figure 15: Results for scenario II (number of walkers surpassing the number of landmarks).

Figure 8

 8 and 9 invite us to believe in a positive answer even if the points are not actually evenly distributed (they come from a laser scan), thus we may wonder what are actually the hypotheses needed by the conjecture. Question 16. What hypotheses a sampling of a bounded δ-dimensional manifold embedded in the d-dimensional space should verify such that the Delaunay triangulation satisfies the Distribution Condition with F(n) = n 1/δ ?

Table 1

 1 gives a succinct summary of previous works and our contributions.

		Jump	Keep, Jump Delaunay Keep, Jump,
		& Walk	& Walk	hierarchy	& Climb
		[39, 22]	(Section 5)	[19]	(Section 6)
	distribution-sensitive	no	yes	no	yes
	expected query complexity O(n 1/(d+1) )	O(n 1/(d+1) )	O(log n)	O(log #(pq))
	time to answer 2 20 queries	8s to 25s	5s to 10s	5s to 12s	1s to 11s

Table 1 :

 1 Overview of paper's contributions.

New results from this paper are in boldface, the ranges of time correspond to the performance obtained for different scenarios; more details on the experiments are available in Section 7.

Table 2 :

 2 Data sets in 2D and 3D.

	simplices	400 600 800 1000 1200 1400 1600	1M points evenly distributed on an ellipsoid		simplices	100 200 300 400	1M points evenly distributed in a unit cube		simplices	800 200 400 600	1M points on Pooran's Hand			simplices	800 200 400 600	1M points on Galaad
		200
		0						0						0						0
		0	0.2	0.4	0.6	0.8	1	0	0.2	0.4	0.6	0.8	1	0	0.2	0.4	0.6	0.8	1	0	0.2	0.4	0.6	0.8	1
				length					length					length					length

Table 3 :

 3 Our choices for the exact number of landmarks. These formulas are taken for models with more than around 600K vertices.

Actually, the Delaunay triangulation been given as input, Jump & Walk belongs to the "sub-linear geometric algorithm" category introduced by Chazelle et al.[START_REF] Chazelle | Sublinear Geometric Algorithms[END_REF].

All these point location strategies are also implemented in a javascript demo; we made it available at[START_REF] De Castro | A pedagogic JavaScript program for point location strategies. Demo[END_REF].

Acknowledgments

The authors wish to thank FACEPE/INRIA, APQ-0055-1.03/12, for financial support, and Aim@shape for providing the realistic models.

* This work is partially supported by ANR Project Triangles and Région PACA.

sequence S of k query points lying in C is, from Eq.(3), at most

since, by Theorem 3, EM IT = O(k 1-1/d ). Therefore, W (k) has an expected amortized O F(n) • k -1/d + 1 complexity for k queries.

Combining various options for F(n) and the data-structure to store the landmarks, gives us some interesting possibilities. The trick is always to balance these different costs, since increasing one decreases another.

Jump & Walk. Classical Jump & Walk uses a simple data-structure (e.g. a list) to store the random sample of T and assumes

Here, we use the same data-structure to store the set of landmarks. Keep step decides whether the query is kept at a landmark and inserts it if needed. This takes K(k) = O(1). Jump step takes J(k) = O(k). Then, using Lemma 13 and taking k = n 1/(d+1) landmarks amongst the queries ensures an amortized query time of O(n 1/(d+1) ). It is noteworthy that the complexity obtained here matches the classical Jump & Walk complexity with no hypotheses on the distribution of query-points (naturally, the queries must lie in the region C, which in turn must lie inside the domain of T , see Section 3).

Outside this classical framework, Jump & Walk has some interests, even with weaker hypotheses. In general considering Lemma 13, taking k = F(n) 1-1/(d+1) balances the jump and the walk costs. Another remark is that if the landmarks are a random subset of the vertices of T (as is the classical Jump & Walk), then the cost of the walk is F(n/k) [19, Variation of Lemma 4]. Assuming F(j) = O(j β ), the jump and the walk costs are balanced by taking k = n 1-1/(β+1) in this case.

Besides, if Conjecture 2 is verified, Keep, Jump, & Walk should use a sample of size

to construct Delaunay triangulation for points on a hypersurface, and not O(n 1/(d+1) ) as for random points in the space. In particular, k should be O(n 2/3 ) in 2D, and O(n 3/8 ) in 3D; this is verified experimentally in Section 7.3, and should be applied in surface reconstruction applications. Despite Jump & Walk's non-optimality, for up to few millions of points, if the number of landmarks is carefully chosen, this strategy might be actually competitive; see Section 7.3, and Section 7.4.

Walk & Walk. In Walk & Walk, the data-structure to store the landmarks is a Delaunay triangulation L, in which it is possible to walk (notice that T may not be a Delaunay triangulation). Assuming a random order on the landmarks, inserting or deleting a landmark after location takes K(k) = O(1) and jump step takes

If the queries and the sites are both evenly distributed we get J(k) = O(k 1/d ) and, by Lemma 13,

√ n to balance the jump and walk costs. Finally, the point location takes expected amortized time O(n 1/2d ).

If walking inside T and L takes linear time, k = n 1-1/(d+1) balances Walk & Walk costs. Delaunay Hierarchy of Queries. A natural idea is to use several layers of triangulations, walking at each level from the location at the coarser layer. When the landmarks are vertices of T and each sample takes a constant ratio of the vertices at the level below, this idea yields the Delaunay hierarchy [START_REF] Devillers | The Delaunay hierarchy[END_REF].

We can handle bad triangulations by looking at the tradeoff between query time and storage. If the region C of T is such that F(n) is a polynomial on n, and queries are well-distributed, we can get interesting query time once a polynomial storage is allowed. More precisely, if the queries are such that a random sample of the queries has a Delaunay triangulation of expected linear size (always true in 2D), then using a random sample of k queries for the landmarks and a Delaunay hierarchy to store L, gives K(k) = J(k) = O(log k). Then by Lemma 13 we have W (k) = O(k -1/d • F(n)) (amortized) and taking k = F(n) d / log d n balances jump and walk costs, leading to an expected amortized logarithmic query time.

The conditions such that Walk & Walk and the Delaunay Hierarchy of Queries are interesting are quite restrictive on n and on the discrepancy between the sites and queries distribution, thus they are mentioned here but they are not tried in the benchmarks section.