Matteo Frigo

Samuel Deslauriers-Gauthier

Drew Parker

Abdol Aziz

Junghoon Ould Ismail

John Kim

Ragini Verma

Rachid Deriche

Effects of tractography filtering on the topology and interpretability of connectomes

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The analysis of connectomes and their associated network metrics forms an important part of clinical studies [START_REF] Bullmore | Complex brain networks: graph theoretical analysis of structural and functional systems[END_REF][START_REF] Sharp | Network dysfunction after traumatic brain injury[END_REF]. These connectomes are based on tractography algorithms to estimate the structural connectivity between brain regions [START_REF] Maier-Hein | The challenge of mapping the human connectome based on diffusion tractography[END_REF]. However, tractography algorithms, are prone to false positive connections [START_REF] Maier-Hein | The challenge of mapping the human connectome based on diffusion tractography[END_REF] and this affects the quality of the connectomes. Several tractography filtering techniques (TFTs) [START_REF] Frigo | Resolving the crossing/kissing fiber ambiguity using Functionally Informed COMMIT[END_REF][START_REF] Daducci | COMMIT: convex optimization modeling for microstructure informed tractography[END_REF][START_REF] Smith | SIFT2: Enabling dense quantitative assessment of brain white matter connectivity using streamlines tractography[END_REF] have been proposed to alleviate this issue in studies [START_REF] Frigo | Reducing false positive connection in tractograms using joint structure-function filtering[END_REF][START_REF] Daducci | Microstructure informed tractography: pitfalls and open challenges[END_REF][START_REF] Smith | The effects of SIFT on the reproducibility and biological accuracy of the structural connectome[END_REF], but their effect on connectomic analyses of pathology has not been investigated. The aim of our work is to investigate how TFTs affect network metrics and their interpretation in the context of clinical studies.

Methods

Our dataset consisted of 18 patients with Traumatic Brain Injury (TBI) and 18 demographically matched healthy controls. For each subject, the connectomes were created using probabilistic anatomically constrained tractography to obtain a tractogram of 2 million streamlines, parcellating the brain into 86 regions based on the Desikan atlas [START_REF] Desikan | An automated labeling system for subdividing the human cerebral cortex on MRI scans into gyral based regions of interest[END_REF], and using the streamline count to represent the connectivity between regions. We refer to this 86 x 86 matrix as the "unfiltered connectome". TFTs filter a tractogram by assigning weights to streamlines based on how well they explain the underlying data. Streamlines associated with a coefficient of zero value are marked as a false positive, and are hence excluded from the tractogram. The TFTs we compare are SIFT2 [START_REF] Smith | SIFT2: Enabling dense quantitative assessment of brain white matter connectivity using streamlines tractography[END_REF], COMMIT [START_REF] Daducci | COMMIT: convex optimization modeling for microstructure informed tractography[END_REF] and the Group-Sparsity (GS) formulation of COMMIT [START_REF] Frigo | Resolving the crossing/kissing fiber ambiguity using Functionally Informed COMMIT[END_REF]. SIFT2 filters the tractogram based on the fiber density information without incorporating microstructure. On the other hand, COMMIT models the underlying microstructure and excludes false positives based on how well the streamlines explain the acquired dMRI fitted with this multi-compartment model. Finally GS builds on this microstructure model of COMMIT and incorporates the brain's bundle structure to eliminate false positives. Starting from unfiltered connectomes, new "kept" connectomes were recreated after filtering each tractogram using these 3 TFTs. We also computed the connectomes using the streamlines that have been excluded by the process of filtering by COMMIT and GS, called "excluded" connectomes. The topology of connectomes was quantified using the integration measure of global efficiency and the segregation measure of Louvain modularity, computed on healthy controls. The interpretability of the connectomes was evaluated by comparing the connectomes of the patients and controls at the level of each edge, using the Mann-Whitney U test with false discovery rate based multiple comparisons correction.

Results

Fig. 1 illustrates that all TFTs increase the segregation and decrease the integration of the connectomes, which translates into a significant change on the network topology. Fig. 2 shows the comparison of patients and controls for each of the connectome sets. We observe that SIFT2 and COMMIT increase discriminability between patients and healthy controls, as compared to the unfiltered connectomes, while GS removes all differences. Notably, although SIFT2 and NNLS both capture group differences, different sets of edges show significant differences and could potentially involve different subnetworks. In addition, although there are no significant group differences in the excluded connectomes of COMMIT, all group differences in GS are transferred to the excluded connectome.

Conclusions

Our results demonstrate that tractography filtering techniques change the topology of brain networks, and thus alter network metrics. The uniform removal of false positives that COMMIT undertakes, has a different effect than the structured removal of GS. This clearly affects the interpretability of results, as we demonstrated i in the TBI dataset. As such, more research and extra caution are needed prior to incorporating tractography filtering into connectomic analysis pipeline in clinical studies.

Figure 2

Effect of tract filtering on the interpretability of connectomic analysis of a clinical dataset. These figures show the results of the edge-wise statistical comparison of connectomes of patients with brain injury using the Mann-Whitney U test with FDR multiple comparisons correction on A) unfiltered connectomes; B) SIFT2 connectomes; C) and D) connectomes based on streamlines kept and removed after COMMIT, respectively; E) and F) Connectomes created using streamlines kept and removed by GS, respectively.

Figure 1

 1 Figure 1 Effect of tract filtering on the topology of connectomes of the healthy controls.Figure A shows the intra-subject variability of the modularity across different Tractography Filtering Techniques. The displayed values are the average of 100 runs of the Louvain modularity method. Figure B shows the intra-subject across-TFT variability of efficiency. Both integration and segregation of the network topology is affected by tract filtering.

Acknowledgements

This work is supported by funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (ERC Advanced Grant agreement No 694665 : CoBCoM -Computational Brain Connectivity Mapping) and NIH R01NS065980, PA-Department of Health PACT award and NIH R01NS096606.


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

Olivier Devillers
email: olivier.devillers@inria.fr

Kunal Dutta
email: kunal.dutta@inria.fr

Marc Glisse
email: marc.glisse@inria.fr

Randomized incremental construction of Delaunay triangulations of nice point sets

Keywords: 2012 ACM Subject Classification I.3.5 Computational Geometry and Object Modeling Randomized incremental construction, Delaunay triangulations, Voronoi diagrams, average-case analysis, probabilistic analysis

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice.

Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points in E d or on polyhedral surfaces in E 3 has linear complexity, as opposed to a worst-case complexity of Θ(n d/2 ) in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value.

Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Introduction

The randomized incremental construction (RIC) is an algorithmic paradigm introduced by Clarkson and Shor [START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF], which has since found immense applicability in computational geometry, e.g. [START_REF] Mulmuley | Computational geometry -an introduction through randomized algorithms[END_REF][START_REF] Motwani | Randomized Algorithms[END_REF]. The general idea is to process the input points sequentially in a random order, and to analyze the expected complexity of the resulting procedure. The theory developed by Clarkson and Shor is quite general and led to numerous algorithms that are simple and efficient, both in theory and in practice. On the theory side, randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. Randomized incremental constructions appear also to be very efficient in practice, which, together with their simplicity, make them the most popular candidates for implementations. Not surprisingly, the cgal library includes several randomized incremental algorithms, e.g. for computing Delaunay triangulations.

Experimental evidence has shown that randomized incremental constructions work well beyond the worst-case, which is fortunate since worst-case situations are rare in applications.

This paper aims at extending the analysis of RIC to the case of average-case complexity.

More precisely, our goal is to understand how randomized incremental constructions behave when the input is nice in the sense that the associated construction is significantly smaller than in the worst-case.

We need a model of good point sets to describe the input data and analyze the algorithms. This will be done through the notion of ε-nets, which have a long and rich history since their introduction in the 1950's in the works of Kolmogorov and others on functional analysis and topological vector spaces (see e.g. [START_REF] Tikhomirov | Entropy and -Capacity of sets in functional spaces[END_REF]). ε-nets have become ubiquitous in many theoretical as well as applied areas, from geometry, functional analysis to probability theory and statistics, where they are often used as countable or finite approximations of continuous spaces.

When we enforce such a hypothesis of "nice" distribution of the points in space, a volume counting argument ensures that the local complexity of the Delaunay triangulation around a vertex is bounded by a constant (dependent only on the dimension).

Unfortunately, to be able to control the complexity of the usual randomized incremental algorithms [START_REF] Devillers | The Delaunay hierarchy[END_REF][START_REF] Boissonnat | On the randomized construction of the Delaunay tree[END_REF][START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF][START_REF] Amenta | Incremental constructions con BRIO[END_REF], it is not enough to control the final complexity of the Delaunay triangulation. We need to control also the complexity of the triangulation of random subsets.

One might expect that a random subsample of size k of an ε-net is also an ε -net for ε = ε d n k .

Actually this is not quite true, it may happen with reasonable probability that a ball of radius O (ε ) contains Ω(log k/ log log k) points or that a ball of radius Ω(ε d √ log k) does not contain any point. For the convenience of the reader, we briefly sketch the proofs in the Appendix (Lemma 45). However, it can only be shown that such a subsample is an

Ä ε log(1/ε) ä -covering
and an (ε log(1/ε))-packing, with high probability. Thus this approach can transfer the complexity of an ε-net to the one of a random subsample of an ε-net but with an extra multiplicative factor of Ω(log 1/ε) = Ω(log n). It follows that, in the two cases we consider, the standard analysis does not provide accurate bounds on the complexity of the (standard) randomized incremental construction. Our results are based on proving that, in expectation, the above bad scenarios occur rarely, and the algorithm achieves optimal run-time complexity.

Related Work:

The Delaunay triangulations of nicely-distributed points have been stud-ied since the 50's, e.g. in the work of Meijering [START_REF] Meijering | Interface area, edge length, and number of vertices in crystal aggregates with random nucleation[END_REF], Gilbert [START_REF] Gilbert | Random subdivisions of space into crystals[END_REF], Miles [START_REF] Miles | The random division of space[END_REF] Møller [START_REF] Møller | Random tessellations in R d[END_REF],

Golin-Na [START_REF] Golin | On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes[END_REF], for Poisson-distributed points, Dwyer [START_REF] Dwyer | Higher-dimensional Voronoi diagrams in linear expected time[END_REF][START_REF] Dwyer | The expected number of k-faces of a Voronoi diagram[END_REF] for uniformly distributed points, Attali-Boissonnat [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF], Attali-Boissonnat-Lieutier [START_REF] Attali | Complexity of the Delaunay Triangulation of Points on Surfaces: the Smooth Case[END_REF], Amenta-Attali-Devillers [START_REF] Amenta | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra[END_REF], and others for (ε, κ)-samples, and Erickson [START_REF] Erickson | Nice Point Sets Can Have Nasty Delaunay Triangulations[END_REF]19] for points with bounded spread (the ratio between the maximum to minimum distance between any two points). Except for a few authors such as Dwyer [START_REF] Dwyer | Higher-dimensional Voronoi diagrams in linear expected time[END_REF] and Erickson [19], most of the above results discuss only the combinatorial aspects and not the algorithmic ones. For Poisson and uniformly distributed point samples, we observe that the standard analysis of the RIC procedure immediately implies a bound on the expected run-time, of the order of the expected number of simplices times a logarithmic factor, which is optimal. However, for deterministic notions of nice distributions such as ε nets, (ε, κ) samples, and bounded spread point sets, the standard RIC analysis is not optimal, since, as we observed, it gives at least an extra logarithmic factor for (ε, κ) samples and even worse for bounded spread point-sets, as stated in an open problem by Erickson [19]. Miller, Sheehy and Velingker [START_REF] Gary | A fast algorithm for well-spaced points and approximate delaunay graphs[END_REF] follow a very different approach, giving an algorithm to compute the approximate Delaunay graph of a nicely-spaced superset of points for an arbitrary input point-set, with optimal time complexity and a 2 O(d) -dependence on the dimension. However their algorithm is quite complicated and uses several subroutines that have varying difficulties of implementation. The RIC, while having a worse 2 O(d 2 ) dependence on the dimension (which Miller et al. observe, may be impossible to avoid for computing the exact Delaunay graph), computes the entire Delaunay triangulation of the given point set rather than a superset, is easy to implement and works efficiently in practice.

Our contribution:

We consider two main questions in this paper. First, we consider the case of an ε-net in the periodic space of dimension d, which, as mentioned before, have linear complexity instead of the worst-case Θ(n d/2 ). The reason to consider a periodic space is to avoid dealing with boundary effects that would distract us from the main point, and the fact that periodic spaces are often used in practice, e.g. in simulations in astronomy, biomedical computing, solid-state chemistry, condensed matter physics, etc. [START_REF] Caroli | Delaunay triangulations of closed Euclidean dorbifolds[END_REF][START_REF] Levitt | How hydrophobic buckminsterfullerene affects surrounding water structure[END_REF][START_REF] Robins | Betti number signatures of homogeneous poisson point processes[END_REF][START_REF] De Fabritiis | Multiscale dissipative particle dynamics[END_REF][START_REF] Van De Weygaert | Alpha shape topology of the cosmic web[END_REF]. Following this, we deal with ε-nets on a polyhedral surface of E 3 , which is also a commonly-occuring practical scenario in e.g. surface reconstruction [START_REF] Amenta | Surface Reconstruction by Voronoi Filtering[END_REF][START_REF] Boissonnat | Smooth surface reconstruction via natural neighbour interpolation of distance functions[END_REF], and has Delaunay triangulations with linear, as opposed to the worst-case quadratic, complexity. In this case, the boundary effects need to be explicitly controlled, which requires a more careful handling along with some new ideas. In both cases, we establish tight bounds and show that the complexity of the usual RIC is O(n log n), which is optimal. Hence, without any modification, the standard RIC nicely adapts to the good cases above.

Our technical developments rely on a general bound for the probability of certain nonmonotone events in sampling without replacement, which may be of independent interest.

Extensions

We also give some extensions of our results for periodic spaces. Our extensions are in four directions: (i) a more general notion of well-distributed point sets, the (ε, κ) samples (ii) a different notion of subsampling -the Bernoulli or i.i.d. sample where each point is selected to be in Y independently of the others, with probability q = s/n, (iii) a more general class of spaces -Euclidean d-orbifolds, and (iv) a more general class of metrics -those having bounded-distortion with respect to the Euclidean metric. Precisely, for all the above cases, we show that the Delaunay triangulation of a random subsample has a linear size in expectation. We believe that our methods should work for an even larger class of spaces, though this might require more delicate handling of boundary effects and other features specific to the metric space under consideration.

C V I T 2 0 1 6

23:4

RIC of Delaunay triangulations of nice point sets

Outline The rest of the paper is as follows. In Section 2, we define the basic concepts of Delaunay triangulation, ε-net, flat torus and random samples. We state our results in Section 3. In Section 4, we bound the size of the Delaunay triangulation of a uniform random sample of a given size extracted from an ε-net on the flat torus T d . In Section 5, we analyse the case when the uniform random subsample is drawn from an ε-net on a polyhedral surface in E 3 . In Section 6, we use the size bounds established in Sections 4 and 5, to compute the space and time complexity of the randomized incremental construction for constructing Delaunay triangulations of ε-nets. Finally, in Section 7, we state and prove some extensions.

Proofs missing from the main sections are given in the Appendix.

Background

Notations

We

V d = π d 2 Γ( d 2 +1) and S d = 2πV d-1 , where Γ(t) := ∞ 0 e -x x t-1 dx, (t > 0) denotes the Gamma function. For d ∈ Z + , Γ(d + 1) = d!. We note that 2 d d -d/2 ≤ V d ≤ 2 4d d -d/2
(see e.g. [34]).

For an event E in some probability space Ω, we use 1 [E] to denote the indicator variable

1 [E] = 1 [E] (ω) which is 1 whenever ω ∈ E,

ε-nets

A set X of n points in a metric space M, is an ε-packing if any pair of points in X are at least distance ε apart, and an ε-cover if each point in M is at distance at most ε from some point of X . X is an ε-net if it is an ε-cover and an ε-packing simultaneously.

The definition of an ε-net applies for any metric space. In the case of the Euclidean metric, we can prove some additional properties. We shall use . to denote the Euclidean 2 norm. The following lemmas are folklore.

:= E d /(kZ) d .
Lemma 3 (ε-net size bounds). Given ε ∈ (0, 1/2], let X be an ε-net over the flat torus T d .

Then,

(X ) ∈ [d d/2 2 -4d • ε -d , d d/2 ε -d ].
Proof. Observe that, by the minimum distance property of the points in X , the balls of radius ε/2 centered around each point in X are disjoint, and by a volume argument there can be at most 1

V d ×(ε/2) d ≤ 2 -d d d/2 (ε/2) -d = d d/2 ε -d such balls in T d .
The balls of radius ε centered around each point in X cover the space thus their number is at least 1

V d ×ε d ≥ d d/2 2 -4d • ε -d .
This completes the proof of the lemma.

Delaunay triangulation

For simplicity of exposition and no real loss of generality, all finite point sets considered in this paper will be assumed to be in general position, i.e. no set of d + 2 points lie on a sphere. Given a set X in some ambient topological space, the Delaunay complex of X is the (abstract) simplicial complex with vertex set X which is the nerve of the Voronoi diagram of X , that is, a simplex σ (of arbitrary dimension) belongs to Del(X ) iff the Voronoi cells of its vertices have a non empty common intersection. Equivalently, σ can be circumscribed by an empty ball, i.e. a ball whose bounding sphere contains the vertices of σ and whose interior contains no points of X .

The Delaunay complex is a triangulation if it triangulates the ambient space, or more precisely, the Delaunay complex Del(X ) of a point set X over an ambient space M, is said to be a Delaunay triangulation of M if there exists a homeomorphism between Del(X ) and M. Given a set X in some ambient space M, with its Delaunay complex Del(X ), the star of a subset S ∈ X , or star(S), is the set of all simplices in Del(X ) which are incident to at For example, T d k forms a k d -sheeted covering space of T d , with the covering map x → x mod 1, the modulus operation being defined coordinate-wise. Caroli and Teillaud [START_REF] Caroli | Delaunay triangulations of closed Euclidean dorbifolds[END_REF] showed Theorem 4 ). The Delaunay complex of any finite point set in T d having at least 1 point, embeds in the 3 d -sheeted covering of T d . If the maximum circumradius of a simplex is at most 1/2, then the complex embeds in T d itself.

Note that the above theorem implies that the Delaunay triangulation of any finite point set in T d always exists in the 3 d -sheeted covering of T d .

A key property of ε-nets is that their Delaunay triangulations have linear size.

C V I T 2 0 1 6

23:6

RIC of Delaunay triangulations of nice point sets Lemma 5 (Talmor [30]). Let ε ∈ (0, 1/2] be given, and let X be an ε-net over T d . Then the Delaunay triangulation of X , Del(X ) has at most 4 d 2 ε -d simplices.

Proof. Observe that the circumradius of any simplex in Del(X ) cannot be greater than ε, since this would imply the existence of a ball in T d of radius at least ε, containing no points from X . Therefore given a point p ∈ X , any point which lies in a Delaunay simplex incident to p, must be at most distance 2ε from p. Again by a volume argument, the number of such points is at most

V d ×(2ε+ε/2) d V d ×((ε/2) d ) = 5 d .
Thus, the number of Delaunay simplices of dimension at most d that contain p, is at most the complexity of the Delaunay triagulation in T d on 5 d vertices. This is at most (5 d ) d/2 .Thus we can conclude that the number of simplices in Del(X ) is at most the cardinality of X , times the maximum number of simplices incident to any given point p ∈ X . Now using Lemma 3, we get that

(5 d ) d/2 • (X ) ≤ (5 d ) d+1 2 d d/2 ε -d ≤ 4 d 2 ε -d .

Randomized incremental construction and random subsamples

For the algorithmic complexity aspects, we state a version of a standard theorem for the RIC procedure, (see e.g. [START_REF] Devillers | Randomization yields simple o(n log n) algorithms for difficult ω(n) problems[END_REF]). We first need a necessary condition for the theorem. When a new point p is added to an existing triangulation, a conflict is defined to be a previously existing simplex whose circumball contains p. Condition 6. At each step of the RIC, the set of simplices in conflict can be removed and the set of newly introduced conflicts computed in time proportional to the number of conflicts.

We now come to the general theorem on the algorithmic complexity of RIC using the

O(n log n).

A subset Y of set X is a uniform random sample of X of size s if Y is any possible subset of X of size s with equal probability. In case the multiplicity of a point in X is greater than 1, the sample counts only one copy of the point; all other copies are present in Y if and only if the original point is present.

In order to work with uniform random samples, we shall prove a lemma on the uniformly random sampling distribution or sampling without replacement, which is stated below, and will be a key probabilistic component of our proofs. The lemma provides a bound on the probability of a non-monotone compound event, that is, if the event holds true for a fixed set of k points, there could exist supersets as well as subsets of the chosen set for which the event does not hold. This may well be of general interest, as most natural contiguity results

with Bernoulli (i.e. independent) sampling, are for monotone events. of C having size a, the probability that A contains B and is disjoint from T , is at most

a c b Ä 1 -t c-b ä a-b ≤ a c b • exp -at 2c
, where a, b, c are the cardinalities of A, B, and C respectively, and the cardinality of T is at least t.

Proof. The total number of ways of choosing the random sample A is c a . The number of ways of choosing A such that B ⊂ A and T ∩ A = ∅, is c-b-t a-b . Therefore the required probability is

P [B ⊂ A, T ∩ A = ∅] = c-b-t a-b c a = b-1 i=0 (a -i) a-1 i=b (a -i) b-1 i=0 (c -i) a-1 i=b (c -i) • a-b-1 i=0 (c -b -t -i) a-b-1 i=0 (a -b -i) = b-1 i=0 (a -i) b-1 i=0 (c -i) a-b-1 i=0 (c -b -t -i) a-b-1 i=0 (c -b -i) = (a/c) b b-1 i=0 (1 -i/a) b-1 i=0 (1 -i/c) Å 1 - t c -b ã a-b a-b-1 i=0 (1 -i c-b-t ) a-b-1 i=0 (1 -i c-b ) ≤ (a/c) b Å 1 - t c -b ã a-b ,
where in the last step, observe that for the product

b-1 i=0 (1-i/a) b-1 i=0 (1-i/c) for each i, the term (1 -i/a)
in the numerator is smaller than the corresponding term (1 -i/c) in the denominator, since a ≤ c. A similar observation holds for the product

Å a-b-1 i=0 (1-i c-b-t ) a-b-1 i=0 (1-i c-b ) ã . Now, observe that Ä 1 -t c-b ä a-b ≤ exp Ä - Ä t(a-b) c-b ää ≤ exp -at 2c , if b ≤ a/2 and b < c.

Results

Random samples of ε-nets in T d : The following theorem gives a constant bound on the expected size of star(p) for the Euclidean metric on the flat torus T d .

Theorem 9 (Euclidean metric). Given an ε-net X in T d in general position, where ε ∈ (0, 1 4 ],

the expected number of simplices incident to a point p ∈ X , E [ (star(p))] in the Delaunay

triangulation of a uniform random sample S ⊂ X of size s ≥ 4(2 √ d) d d 3 + 1 containing p, is less than 2 • 6 d 2 +d .
Polyhedral Surfaces in E 3 : A polyhedral surface S in E 3 is a collection of a finite number of polygons F ⊂ S, called facets, which are pairwise disjoint or meet along an edge. In this paper, S will denote an arbitrary but fixed polyhedral surface, with C facets, and having total length of the boundaries of its faces L and total area of its faces A.

We show that the expected complexity of the Delaunay triangulation of a uniformly random subsample of an ε-net on a polyhedral surface is linear in the size of the subsample: Extensions: Finally, our extensions are stated and proved in Section 7.

Theorem 10. Let ε ∈ [0, 1], X be an ε-net

Euclidean Metric on T d

In this section, we prove that a subsample Y of a given size s, drawn randomly from an ε-net

X ⊂ T d ,

Existence of Delaunay triangulation Del(Y)

In order to ensure we always have the Delaunay complex embedded in T d , we shall use

Proof Framework

Now we set up the formal proof. Recall that n := (X ). Define q := s-1 n-1 . Define

δ := ε • Ä 2d q ä 1/d . Let I 0 := [0, δ), I k := [2 k-1 δ, 2 k δ) for k > 0.
n k := min τ ∈Sp(k) { (B(c σ , r σ ) ∩ X ) : σ = τ ∪ {p}}. For τ ∈ S p (k), let P p (k) denote an
upper bound on the probability that σ = τ ∪ {p} appears in Del(Y), that is,

P p (k) := max τ ∈Sp(k) {P [σ ∈ Del(Y)]}.
Finally, let Z p (k) denote the number of simplices τ ∈ S p (k) such that σ ∈ Del(Y). The main lemma in the proof is a bound on the expected complexity of the star of p, in terms of s p (k)

and P p (k).

Lemma 12. E [ (star(p))] ≤ k≥0 E [Z p (k)] ≤ k≥0 s p (k) • P p (k).
Proof. For a simplex σ = τ ∪ {p}, with the vertex set of τ in S p (k), let 1 [τ ] be the indicator random variable which is 1 if σ ∈ star(p), and zero otherwise.

Then Z p (k) := τ ∈Sp(k) 1 [τ ] ,
and (star(p)) = k≥0 Z p (k).

Taking expectations over the random sample Y, we get

E [ (star(p))] = k≥0 E [Z p (k)] = k≥0 τ ∈Sp(k) E 1 [τ ] ≤ k≥0 τ ∈Sp(k) P d (k) = k≥0 s p (k) • P d (k).
It only remains, therefore, to establish bounds on s p (k) and P p (k) as functions of k, and finally to bound the sum k≥0 s p (k)

• P p (k).
Following the earlier discussion on the existence of the Delaunay triangulation Del(Y),

we shall split the sum k≥0 E [Z p (k)] into the two regimes, 0 ≤ k ≤ k max , and k > k max ,
where k max denotes log 2 1 4δ .

Case I: Simplices with small circumradii k ∈ [0, k max ]

In this regime, the circumradii r σ of the potential simplices, are at most 1/4, since recall that by the definition of k max , we have r σ ≤ 2 kmax = 1/4. Therefore every set of d + 1 vertices in Y, has a unique circumball. We begin by establishing a bound on P p (k). First, we bound n k from below using Lemma 2.

Lemma 13. Let σ be a simplex incident to p, having circumradius r σ ∈ I k , k ≥ 0.

n k ≥ 0 k = 0. Ä 2 k-1 δ ε ä d 0 < k ≤ k max .
Proof. When k ≤ k max , the radius of the circumball of a simplex σ = τ ∪ {p}, τ ∈ S p (k), is at most 2 kmax δ ≤ 1/4 < 1/2. Applying Theorem 4, we work in the one-sheeted covering of T d . Using the fact that X is an ε-covering, we apply Lemma 2 to get that

n k ≥ (2 k-1 δ/ε) d .
Now applying Lemma 8, we can bound P p (k).

Lemma 14. For k ≥ 0, P p (k) ≤ q d • exp (-qn k /2).
Proof. The simplex σ can be a Delaunay simplex only if (i) the set of its vertices is included in the subsample Y, and (ii) all points in B(c σ , r σ ) ∩ X are excluded from Y. The idea is therefore, to use Lemma 13 to bound the number of points in B(c σ , r σ ) ∩ X from below by n k , and then upper-bound the probability that all these points are excluded from Y.

This suggests applying Lemma 8, with the universe having c = n -1 elements, sample size a = s -1, included set having b = d elements, and excluded set having t = n k elements.

We verify first that the conditions of the lemma are satisfied, i.e. (i) b ≤ min{ a 2 , c -1}, since s ≥ 4d + 1. Now applying the lemma, we get

P [σ ∈ Del(Y)] ≤ Å s -1 n -1 ã d exp Å -n k • Å s -1 2(n -1) ãã = q d • exp (-qn k /2) ≤ q d • exp (-qn k /2) ,
where the equality was by the substitution q = s-1 n-1 , and the last inequality followed from Now we can bound s p (k) using the above observation together with Lemma 1.

the fact that d = b ≤ c -1 = n -2.
Lemma 16. For k ≥ 0, s p (k) ≤ (6•2 k δ/ε) d 2 d!
.

Proof. Let τ be an element of S p (k). Using Lemma 15 and the definition of S p (k), we

have that σ = τ ∪ {p} ⊂ B[p, 2 k+1 δ]. If k ≤ k max , then 2 k+1 δ ≤ 1/2.
• 2 k δ/ε) d 2 /d!.
Next, using the above bounds on s p (k) and n k , we shall bound the sum

kmax k=0 E [Z p (k)]
in the following three lemmas.

Lemma 17. E [Z p (0)] ≤ 6 d 2 +d .
Proof. Substituting the bounds on s p (0) and P p (0) proved in Lemmas 16, 14 and 13 respectively, we have

E [Z p (0)] = s p (0) • P p (0) = (6(δ/ε)) d 2 d! • q d ≤ 6 d 2 • (2d) d d! ≤ 6 d 2 • (2e) d ,
where in the second step we used the definition of δ to get q(δ/ε) d = 2d, and in the last step we used Stirling's approximation d d /d! ≤ e d , and that 2e < 6.

Lemma 18.

kmax k=0 E [Z p (k)] ≤ (1 -(2/e) 6 ) -1 • 6 d 2 +d . Proof. First, recall from Lemma 12 that k≥1 E [Z p (k)] ≤ k≥0 s p (k) • P p (k). Now from
Lemmas 14, 13 and 16, we have that for all k ≥ 0,

(i) s p (k) ≤ sp (k) := (6 • 2 k δ/ε) d 2 /d! and (ii) P p (k) ≤ Pp (k) := ® q d , k = 0 q d • exp -q(2 k-1 δ/ε) d /2 , k ∈ [1, k max ] . Observe that k≥0 s p (k) • P p (k) ≤ k≥0 sp (k) • Pp (k). In order to bound k≥0 s p (k) • P p (k),
it therefore suffices to simply bound k≥0 sp (k) • Pp (k). For the rest of the proof therefore, we shall focus on bounding this sum.

When 1 ≤ k ≤ k max :

Consider the ratio of successive terms sp(k+1)• Pp(k+1)

sp(k)• Pp(k) of the sequence sp (k) • Pp (k) k≥1 .
From Lemmas 16 and 13, we have

sp (k + 1) • Pp (k + 1) sp (k) • Pp (k) = (6 • 2 k+1 δ/ε) d 2 /d! (6 • 2 k δ/ε) d 2 /d! × q d • exp -q(2 k δ/ε) d /2 q d • exp (-q(2 k-1 δ/ε) d /2) = 2 d 2 • exp - q 2 • (2 k-1 δ/ε) d (2 d -1) = 2 d 2 • exp Å - 1 2 • Ä 2 (k-1)d 2d ä (2 d -1) ã ≤ 2 4 e -6 ,
where in the last step we used the definition of δ = ε(2d/q) 1/d , i.e. q(δ/ε) d = 2d. The last step follows by taking k = 1, d = 2, to get 2 4 • e -6 ≤ (2/e) 6 .

When k = 0:

In this case, the ratio sp(1)• Pp( 1)

sp(0)• Pp(0) ≤ 2 d 2 • exp -d • 2 d , which is at most (2/e) 6 for d ≥ 2.
Therefore for all 0 ≤ k ≤ k max -1, we have that sp(k+1) Case II: Simplices with large circumradii k > k max .

In this regime, the circumradii of the potential simplices are greater than 1

E [Z p (k)] = 3 d 2 (n -1) d d! • P p (k) = 3 d 2 (n -1) d d! • q d • exp Ç - q 2 • n -1 (2 √ d) d å ≤ 3 d 2 (s -1) d d! • exp Ç - s -1 2(2 √ d) d å . ( 1
)
For s > s 0 = 4(2 √ d) d • d 3 + 1,
this function is decreasing in term of s and it is easy to check that the value in s 0 is smaller than 5. The lemma follows.

Thus, by Lemmas 12, 18, and 19, the expected complexity of the star of p is at most Main ideas: Our overall strategy will be to mesh the proofs of Attali-Boissonnat [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF] and Theorem 9. Briefly, Attali and Boissonnat reduce the problem to counting the Delaunay edges of the point sample, which they do by distinguishing between boundary and interior points of a facet. For boundary points, they allow all possible edges. For interior points, the case of edges with endpoints on the same facet is easy to handle, while geometric constructions are required to handle the case of endpoints on different facets, or that of edges with one endpoint in the interior and another on the boundary.

(1 -(2/e) 6 ) -1 • 6 d 2 +d + 5 ≤ 2 • 6 d 2 +d for d ≥ 2,
However, we shall need to introduce some new ideas to adapt our previous methods to this setting. Firstly, an edge can have multiple balls passing through its endpoints and, as soon as one of these balls is empty, the edge is in the triangulation. This is handled using a geometric construction (see Lemma 28). Basically, the idea is to build a constant-sized packing of a sphere centered on a given point, using large balls, such that any sphere of a sufficiently large radius which passes through the point, must contain a ball from the packing.

Secondly, since we have randomly spaced points at the boundaries, boundary effects could penetrate deep into the interior. To handle this, we introduce the notion of levels of a surface, instead of the fixed strip around the boundary used in [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF], and use a probabilistic, rather than deterministic, classification of boundary and interior points. The new classification is based on the level of a point and the radius of the largest empty disk passing through it.

Recall the definitions of X , Y and S from Theorem 10. For a curve Γ, l(Γ) denotes its length. For a subset of a surface R ⊂ S, a(R) denotes the area of R. We next present some general lemmas, which will be needed in the proofs of the main lemmas. For sets A, B ⊂ E 3 , A ⊕ B denotes the Minkowski sum of A and B, i.e. the set {x + y : x ∈ A, y ∈ B}. For convenience, the special case A ⊕ B(0, r) shall be denoted by A ⊕ r. Throughout this section, we shall use κ to denote the maximum number of points of an ε-net in a disk of radius 2ε, which is at most 6 d = 36 (using Lemma 1 with r = 2ε and ρ = ε), we and define q := s n , and

δ := ε/ √ q.

Level sets, Boundary points and Interior points

We now introduce some definitions which will play a central role in the analysis. First we define the notion of levels. Given facet F ∈ S and k ≥ 0, define the level set

L ≤k := F ∩ (∂F ⊕ 2 k δ). L =k := L ≤k \ L ≤k-1 . For x ∈ X , the level of x, denoted Lev(x), is k such that x ∈ L =k . Let L ≤k (X ), L =k (X ) denote L ≤k ∩ X , L =k ∩ X respectively. Note that for x ∈ L =k , k ≥ 1, the distance d(x, ∂F ) ∈ (2 k-1 δ, 2 k δ]. Hence, if Lev(x) = k, D(x, 2 k-1 δ) ⊂ F . For k = 0, d(x, ∂F ) ∈ [0, δ].
Next, we define a bi-partition of the point set into boundary and interior points. Given We have the following lemmas, to be proved in section 5.2.

x ∈ F having Lev(x) = k, then x ∈ Bd F (Y),
Lemma 20. E [ (E 1 )] ≤ O(1) • (κ 2 L 2 /A) • s. Lemma 21. E [ (E 2 )] ≤ c 4 • κs, where c 4 ≤ 2 • 10 5 . Lemma 22. E [ (E 3 )] ≤ c 4 • (C -1) • κs. Lemma 23. E [ (E 4 )] ≤ O(1) • κ 2 L 2 A s.
Given the above lemmas, the proof of Theorem 10 follows easily.

Proof of Theorem 10. As in [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF] (Section 4), by Euler's formula, the number of tetrahedra Before proving Lemmas 20-23, we first present a few technical lemmas.

Some Technical Lemmas

The following geometric and probabilistic lemmas prove certain properties of ε-nets on polyhedral surfaces, random subsets, etc., as well as exploit the notion of boundary and interior points to get an exponential decay for boundary effects penetrating into the interior.

Proposition 24 ([4]

). Let F be a facet of S. For any Borel set R ⊂ F , we have

Å a(R) 4πε 2 ã ≤ (R ∩ X ) ≤ Å κ • a(R ⊕ ε) πε 2 ã
, and therefore, (2)

Å A 4πε 2 ã ≤ (S ∩ X ) = n. ( 3
)
Proposition 25 ([4]). Let F be a facet of S, let Γ ⊂ F be a curve contained in F , and

k ∈ N. Then ((Γ ⊕ kε) ∩ X ) ≤ Å (2k + 1) 2 k ã κ l(Γ) ε (4) ≤ Å 9kκ l(Γ) ε ã , when k ≥ 1. ( 5
1 sin β = 1/2 sin α , ⇒ 1 sin(π/2 -α/2) = 1/2 sin α , ⇒ 1 cos(α/2) = 1/2 sin α , ⇒ 4 sin(α/2) = 1.
Therefore, α = 2 arcsin(1/4), or 2α = 4 arcsin (1/4).

Thus, one disk covers an angle of 4 arcsin(1/4), and so the number of required disks having radius 1/2, is at least 2π 4 arcsin(1/4) ≈ 6.21 < 7.

It is now easy to see that we can place the disks on the boundary in a greedy manner, such that they cover the maximum possible angle, except of course the last disk which may have some overlap with the first disk. Thus seven disks would suffice as well.

Lemma 27 (Level Size).

(L =k ∩ X ) ≤ (L ≤k ∩ X ) ≤ 9κL Ä 2 k δ ε 2 ä .
Proof. The first inequality is obvious, as L =k ⊆ L ≤k . The proof of the second inequality follows by applying Proposition 25 over the boundaries of the facets. For a fixed facet F ∈ S, we get

ÇÇ ∂F ⊕ Ç 2 k δ ε å ε å ∩ X å ≤ Ç 9κ2 k δ ε å • Å l(∂F ) ε ã .
Summing over all F ∈ S, we get Lemma 29 (Decay lemma). Given x 1 , . . . , x t ∈ X , such that Lev(x i ) > 0, 1 ≤ i ≤ t, then for all 0 ≤ k i < Lev(x i ), with r * i := 2 ki δ, the probability of the event

(L ≤k ∩ X ) = F ∈S ∂F ⊕ 2 k δ ∩ X ≤ Ç 9κ2 k δ ε 2 å F ∈S l(∂F ) = Ç 9κ2 k δ ε 2 å • L.
E := {∀i ∈ [t] : ∃D i = D(y i , r i ) : r i ≥ r * i , x i ∈ Y, x i ∈ ∂D i and int(D i ) ∩ Y = ∅},
is given by

P [E] ≤ ® q t , if k max = 0, c 1 • q t • exp -c 2 • 2 2kmax , if k max > 0, C V I T 2 0 1 6

23:16

RIC of Delaunay triangulations of nice point sets

where c 1 = c t B , c 2 ≥ 2 -7 , and k max := max i {k i }. Thus

P [E] ≤ c 1 • q t • exp -c 2 • 2 2kmax , k max ≥ 0.
Proof. Firstly, consider the case where k max = 0, i.e. all the k i 's are zero. In this case we simply upper bound the probability of the event E, by the probability of including all the points x 1 , . . . , x t in Y. By Lemma 8, this is at most q t . We next come to the case when k max > 0. Since for all i ∈ [t], k i < Lev(x i ), we can apply Lemma 28 for each i, with k = k i , to conclude that for each i, there exists a collection D i of at most c B disks of radius r * i /4, such that any disk having radius greater than r * i and passing through x i , must contain some disk D * i ∈ D i . Let T denote the set t i=1 D i . By the union bound over the set T , we get

P [E] ≤ P [∃B ∈ T : ∀i ∈ [t], B i ∩ Y = ∅] ≤ (T ) • P [∀i ∈ [t], B i ∩ Y = ∅] ,
where B ∈ T is some fixed element of T .

Let j := arg max i∈[t] k i , so that k max = k j . Now, the event E requires the set x 1 , . . . x t to be in the sample Y, and the interiors of the disks D * i to be free from points in Y. In particular, the disk D * j should not contain any points in Y. Therefore applying Lemma 8 on the universe C = X , the random sample A = Y, the included subset B = {x 1 , . . . , x t }, and the excluded subset

Z = D * j ∩ X of size at least z = π(r * j /4) 2
4πε 2 , we get

P [E] ≤ (T ) • P [∀B i ∈ u, B i ∩ Y = ∅] ≤ (c B ) t • q t • exp Ç - 1 2 q • Ç π(r * j /4) 2 4πε 2 åå ≤ c 1 q t • exp -2 2kmax-7 .
where in the last step we used that q = s/n, δ = n/s • ε, and r * j = 2 kmax δ, and set

c 1 = c t B .
Lemma 30 (Growth Lemma). Given any point x ∈ S in a facet F , and 0 ≤ k < Lev(x),

we have

(i) 2 2k-2 /q ≤ D(x, 2 k δ) ∩ X ≤ 4 • (2 2k /q). (ii) 2 2k-2 ≤ D(x, 2 k δ) ∩ Y ≤ 4 • (2 2k ).
Proof. By the definition of Lev(x), we have that D(x, 2 Lev(x)-1 δ) ⊂ F . Now the statement follows by the application of Proposition 24, as below

π(2 k δ) 2 4πε 2 ≤ D(x, 2 k δ) ∩ X ≤ π(2 k δ + ε) 2 πε 2 , or, 2 2k-2 n s ≤ D(x, 2 k δ) ∩ X ≤ 2 • 2 2k n s ,
where we used that δ := n s ε. This gives the first statement of the lemma, using q = s/n.

The second statement follows simply by taking expectation.

Proofs of Lemmas 20-23

The proofs of Lemmas 20 and 21 now follow from the Decay and Growth lemmas, together with similar ideas as for the flat torus case.

Proof of Lemma 20. Let x 1 , x 2 ∈ Bd S (Y). To bound the expected number of edges in E 1 , we simply bound the number of pairs (x 1 , x 2 ) ∈ Bd S (Y) × Bd S (Y). Let l 1 := Lev(x) and l 2 := Lev(y), and let l := max i (l i ) 2 i=1 . By definition, if l = 0, then x 1 , x 2 ∈ Bd S (Y). For l ≥ 1, we get that x 1 ∈ Bd S (Y) and x 2 ∈ Bd S (Y) only if there exists a disk of radius at least 2 l-1 δ passing through x 1 or x 2 , and containing no points of Y. Therefore to bound the probability that (x 1 , x 2 ) ∈ (Bd S (Y)) 2 , we can apply the Decay Lemma 29, with t = 2, for i ∈ {1, 2}. We get

P [(x 1 , x 2 ) ∈ E 1 ] ≤ P (x 1 , x 2 ) ∈ (Bd S (Y)) 2 ≤ c 1 q 2 • exp -c 2 • 2 2l-2 ≤ c 1 q 2 • exp -c 2 • 2 2l , ( 6
)
where

c 2 = c 2 /4 = 2 -9
. Summing over all choices of levels of x 1 and x 2 , we have

E [ (E 1 )] ≤ l1≥0 (L =l1 ∩ X ) l2≥0 (L =l2 ∩ X ) P (x 1 , x 2 ) ∈ (Bd S (Y)) 2 .
By symmetry, it is enough to assume without loss of generality that l 1 ≥ l 2 , i.e. l = l 1 . Thus,

E [ (E 1 )] ≤ 2 l1≥0 (L =l1 ∩ X ) l1 l2=0 (L =l2 ∩ X ) P (x 1 , x 2 ) ∈ (Bd S (Y)) 2 .
Applying equation ( 6) and the Level Size Lemma 27, we get

E [ (E 1 )] ≤ 2 l1≥0 (L ≤l1 ∩ X ) l1 l2=0 (L ≤l2 ∩ X ) • c 1 q 2 • exp -c 2 • 2 2l1 ≤ 2c 1 q 2 l1≥0 (9κL • (2 l1 δ/ε 2 )) l1 l2=0 (9κL • (2 l2 δ/ε 2 )) • exp -c 2 • 2 2l1 ≤ 2c 1 q 2 (9κL Å δ ε 2 ã ) 2 l1≥0 2 l1 • exp -c 2 • 2 2l1 l1 l2=0 2 l2 .
Using the definitions of q and δ, together with Proposition 24, and writing the terms outside the summation as N 1 , we get

N 1 := 2 • c 1 q 2 9κL δ ε 2 2 = 2c 1 • (9κL) 2 s nε 2 ≤ 4c 1 • 4π(9κL) 2 A
• s, we continue

E [ (E 1 )] ≤ N 1 l1≥0 2 l1 • exp -c 2 • 2 2l1 • 2 • 2 l1 ≤ 2N 1 l1≥0 2 2l1 • exp -c 2 • 2 2l1 .
The summation can be bounded using Lemma 46, to get Hence we have that d(x, y) ≤ 2 l δ.

E [ (E 1 )] ≤ 2N 1 • Å 2 • log 1/c 2 2ec 2 ã = 2N 1 • log 1/c 2 e • c 2 . Now substituting c 2 = 2 -9 gives E [ (E 1 )] ≤ 2 • 10 4 • c 1 • 4π(9κL) 2 A • s.
By the Growth Lemma 30, the expected number of Delaunay neighbours y of a point x

such that d(x, y) ≤ δ is at most E [D(x, δ) ∩ Y] ≤ q • 4 q = 4.
Thus the expected number of edges in E 2 from pairs (x, y) with x, y ∈ Int F (Y) for some F ∈ S, and d(x, y) ≤ δ, is at most

4 • (Y). For longer-distance edges, let k ≥ 1 be such that 2 k-1 δ ≤ d(x, y) ≤ 2 k δ. Taking t = 2, x 1 = x, x 2 = y, k 1 = k -1,
P [{x, y} ∈ E 2 ] ≤ c 1 q 2 • exp -c 2 2 2k-2 ≤ c 1 q 2 • exp -c 2 2 2k ,
where c 2 = c 2 /4. Summing over all possible choices of l ≥ 1, and k ≤ l, we get

E [ (E 2 )] ≤ l≥1 (L =l ∩ X ) l k=1 D(x, 2 k δ) ∩ X • c 1 q 2 • exp -c 2 2 2k ≤ c 1 q 2 Ñ l≥1 (L =l ∩ X ) l k=1 κ2 2k (δ/ε) 2 • exp -c 2 2 2k é ≤ c 1 κq Å qδ 2 ε 2 ã • Ñ l≥1 (L =l ∩ X ) é 2 • (1/2) • log 1/c 2 ec 2 ≤ c 1 κq • c 3 Ñ l≥1 (L =l ∩ X ) é ≤ c 1 κq • c 3 • n = c 4 • κs.
where in the second step we applied the Growth Lemma 30, and in the third step we bounded the sum k≥0 2 2k exp -c 2 2 2k using Lemma 46, and used that q = s/n = ε 2 /δ 2 . Note that c 3 ≤ 4 • 10 3 , and

c 4 := c 1 • c 3 ≤ 2 • 10 5 .
For the proofs of Lemmas 22 and 23, we need some more geometric ideas of [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF].

Proof of Lemma 22. Let x, y ∈ Int S (Y), where x ∈ F and y ∈ F , for some F, F ∈ S. Let F be fixed. To analyse this case, we shall first give a geometric construction of [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF], and state an observation from their proof.

{(x, y) ∈ Y × Y | x ∈ Bd S (Y ), y ∈ V F (x)}).
The main observation is now that since V restricted to F is a sub-division of F , for each y ∈ X ∩ F , there is a unique x = x y ∈ Bd S (Y ) such that y ∈ V F (x). Therefore we get

E 4 (Int(F )) ≤ V F (x)∈V: x∈Bd S (Y ) (V F (x) ∩ Y ) ≤ (Y ∩ F ) .
Since the last bound holds for any choice of Y , taking expectation over all choices we get

E [E 4 (Int(F ))] ≤ E [ (Y ∩ F )] = q • (X ∩ F ) .

Now summing over all faces gives

[E 4 (Int)] ≤ E [ (Y)] = s. Lemma 38. Given a facet F ∈ S, E [E 4 (Bd(F ))] ≤ O(1) • κ 2 L•l(∂F )s A . As a consequence, E [E 4 (Bd(S))] ≤ Ä O(1) • κ 2 L 2 s A ä .
Proof. To compute the expected value of E 4 (Bd(S)), fix a face F ∈ S. Consider a pair of points x, y ∈ X , such that y ∈ F . Let E x,y denote the event {x, y} ∈ E 4 (Bd(F )).

The value of E 4 (Bd) is the number of x, y ∈ X , such that E x,y occurs. Taking expectations,

E [E 4 (Bd(F ))] ≤ x∈X y∈X ∩F P [E x,y ] . ( 7
)
Observe that E x,y occurs only if (i) Let P k1,k2 denote the probability that {x, y} ∈ E 4 (Bd(F )), with Lev(x) = k 1 , and k y (x) = k 2 . Equation ( 7) can be rewritten in terms of k 1 and k 2 as

E [E 4 (Bd(F ))] ≤ k1≥0 (L =k1 ∩ X ) k2≥0 V F ∈V (∂V F ⊕ 2 k2 δ) ∩ X • P k1,k2 .
Applying the Decay Lemma 29 with t = 2, x 1 = x, x 2 = y, k 1 = max{0, k 1 -1} (since

x ∈ Bd S (Y)), and k 2 = max{0, k 2 -1}, we get

P k1,k2 ≤ c 1 q 2 • exp (-f (k * )) ,
where k * := max{0, k 1 -1, k 2 -1}, and f (k * ) = 0 if k * = 0, and c 2 • 2 2k * otherwise, with

c 2 = c 2 /4.
As in the proof of Lemma 20, we shall use symmetry to handle the case where k 1 ≥ k 2 and k 2 > k 1 together. We get

E [E 4 (Bd(F ))] ≤ 2 k1≥0 (L =k1 ∩ X ) k2≤k1 V (x)∈V (∂V (x) ⊕ 2 k2 δ) ∩ X • c 1 q 2 • exp -c 2 2 2k1 .
By the Level Size Lemma 27, we get that (L =k1 ∩ X ) ≤ 9κL2 k 1 δ ε 2

. Using Proposition 25, we

get that {∂V (x) ⊕ 2 k2 δ} ∩ Y ≤ 9κ•l(∂V (x))2 k 2 δ ε 2
. By Proposition 34 (iii), each boundary in the partition V is convex for some x ∈ Bd S (Y). Therefore we need to sum l(∂V (x)) only over the convex curves in ∂V (x), x ∈ Bd S (Y). The length of these curves is at most l(∂F ).

Thus we get

E [E 4 (Bd(F ))] ≤ 2L • l(∂F ) • Å 9κδq ε 2 ã 2 k1≥0 2 k1 k2≤k1 2 k2 c 1 • exp -c 2 • 2 2k1 .
C V I T 2 0 1 6

23:22

RIC of Delaunay triangulations of nice point sets

Using Lemma 46, the above summation is bounded by a constant. This comes to

c 1 • O(1) (9κ)) 2 L•l(∂F )δ 2 q 2 ε 4 = O κ 2 L•l(∂F )s A
, where the last step followed from the lower bound on n in Proposition 24 (3), and the identities q = s/n = δ 2 /ε 2 . Summing y over all facets F in S, we get

E [E 4 (Bd(S))] = Ä O(1) • κ 2 L 2 s A ä .

Randomized Incremental Construction (Proof of Theorem 11)

In this section, we show how theorems 9 and 10 imply bounds on the computational complexity of constructing Delaunay triangulations of ε-nets. Our main tool shall be Theorem 7. However, we need to show first that Condition 6 holds. The standard proof of this (see e.g. [START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF], [START_REF] Boissonnat | On the randomized construction of the Delaunay tree[END_REF], also the discussion in [START_REF] Boissonnat | Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension[END_REF](Section 2. This idea works directly when the Delaunay complex is embedded in the one-sheeted covering of T d . In the 3 d -sheeted covering, there can be at most 3 d 2 simplices formed using a given set of d points and p, and we need to check each of these possible simplices. Thus the time goes up by a multiplicative factor of 3 d 2 . However, as the increase is by a constant factor depending only on the dimension, Condition 6 is still satisfied, albeit with a larger constant. Now Theorem 7 can be applied to get the claimed result.

Euclidean Orbifolds and Bounded-Distortion Metrics

In this section, we shall give some extensions of Theorem 9 and 11. The proofs of our theorems follow by finding covering spaces of bounded multiplicity where the Delaunay complex can be embedded, and generalizing Lemmas 16-19 to such spaces.

Given a space S, ε ∈ [0, 1] and κ ∈ Z + , an (ε, κ)-sample is a set of points for which any ball of radius ε in S, contains at least one point and at most κ points.

Theorem 39. Theorems 9, 10 and 11 hold when the point set is an (ε, κ) sample.

Theorem 40. Theorems 9, 10 and 11 also work for the case when the random sample is an i.i.d. sample with probability parameter q = s/n.

Proof Sketch. The proof is on the lines of Theorems 9 and 10. It is only when computing P p (k) that we make use of the fact that points are selected independently. Here, we get Proof. In this case, the existence of the covering space follows from the algorithmic version of Bieberbach's theorem [START_REF] Bieberbach | Über die Bewegungsgruppen des n-dimensionalen euklidischen Raumes mit einem endlichen Fundamentalbereich[END_REF] by Caroli-Teillaud [START_REF] Caroli | Delaunay triangulations of closed Euclidean dorbifolds[END_REF](Section 4).

directly that P p (k) ≤ q d (1-q) n k ≤ q d •exp (-qn k ).
Theorem 42 (Bieberbach [6], Caroli-Teillaud [START_REF] Caroli | Delaunay triangulations of closed Euclidean dorbifolds[END_REF]).

Embedded metrics with bounded distortion

For a metric d on some domain S embedded in E d , define its distortion κ d (with respect to E d ) to be the minimum λ ≥ 1 such that ∀x, y ∈ S :

1 λ x -y ≤ d(x, y) ≤ λ x -y . A d × d matrix M ∈ E d is positive definite if, for all x = 0 ∈ E d , x M x > 0.
For a positive definite matrix M , define its condition number c M to be the ratio of its maximum to its minimum eigenvalue.

For embedded metrics with bounded distortion, we have: Also, letting ((kZ) d ) * denote the non-identity elements of (kZ)

Conclusion and Remarks

In this paper, we analyzed the behaviour of the usual RIC algorithm for the Delaunay triangulation of nice point sets, focussing on the cases where the ambient space is the flat d-torus or a polyhedral surface in E 3 . Similar questions can be asked for other spaces where the Delaunay triangulation is known to have low complexity for "nice" point sets.

We leave for further research, a more general analysis of RIC of Delaunay triangulations of cases such as polyhedral surfaces in higher dimensions, as well as extending the techniques developed in this paper to the RIC of other geometric problems.

(i) Assuming the ε-net is over the unit cube or unit ball in E d , a volume argument gives that there are Ω(ε -d ) = Ω(k) disjoint balls of radius ε , which will be our "bins". Now choosing k points from the n points in the ε-net is akin to throwing k packets into k bins -with high probability, the maximum load of a bin is Ω( log k log log k ), i.e. there exists a ball of radius ε with Ω( log k log log k ) points.

(ii) Similarly, there are Ω(ε / log k) = Ω(k/ log k) balls of radius ε d √ log k that cover the ε-net, and choosing k points from this covering, can be thought of as an instance of the coupon collector problem: we are allowed k draws (i.e. we choose k points), each draw is one of the "coupons" (i.e. the balls in the covering) with equal probability, and we want the probability that at least one coupon has not been collected, i.e. at least one ball from the covering has no point chosen from it. Now the well-known lower tail of the number of draws taken to collect all coupons in the the coupon collector problem, gives that with high probability, for k = Ω(k/ log k) coupons, and at most O(k log k ) = k draws, all coupons will not be collected, that is, some ball of radius Ω(ε d √ log k) will be empty.

Proofs from Section 5

Lemma 46. Given a > 0, b ∈ (0, 1), the sum n∈Z+ 2 an • exp (-b • 2 an ) is at most

  and zero otherwise. We use[n] to mean the set {1, 2, . . . , n}. Given a discrete set A, (A) denotes its cardinality and, for k ∈ Z + , A k denotes the set of k-sized subsets of A. Given an event A in some probability space, P [A] denotes the probability of A occuring. For a random variable Z in a probability space, E [Z] denotes the expected value of Z. Lastly, e = 2.7182 . . . denotes the base of the natural logarithm.

Clarkson-Theorem 7 .

 7 Shor technique (see e.g. Devillers [14] Theorem 5(1,2)). Let F (s) denote the expected number of simplices that appear in the Delaunay triangulation of a uniform random sample of size s, from a given point set P . Then, if Condition 6 holds and F (s) = O(s), we have (i) The expected space complexity of computing the Delaunay triangulation is O(n). (ii) The expected time complexity of computing the Delaunay triangulation is n s=1 n-s s =

Lemma 8 .

 8 Given a, b, c ∈ Z + , with 2b ≤ a ≤ c, t ≤ c. Let C be a set, and B and T two disjoint subsets of C. If A is a random subset of C, choosen uniformly from all subsets

3 . 6 23: 8 RIC

 368 on a polyhedral surface S, having n points and let Y ⊂ X be a random sub-sample of X having size s. Then the Delaunay triangulation Del(Y) of Y on S has O(s) simplices. Algorithmic Bounds: We next use the above combinatorial bounds to get the space and time complexity of the randomized incremental construction of the Delaunay triangulation of an ε-net on the flat d-torus or on a polyhedral surface in E Theorem 11 (Randomized incremental construction). Let ε ∈ [0, 1/4], and let X be an ε-net in general position over (i) the flat d-dimensional torus T d , or (ii) a fixed polyhedral C V I T 2 0 1 of Delaunay triangulations of nice point sets surface S ⊂ E 3 , then the randomized incremental construction of the Delaunay triangulation takes O(n log n) expected time and O(n) expected space, where n = (X ) and the constant in the big O depends only on d, and not on n or ε. Further, at each step of the randomized incremental construction, the Delaunay complex of the set Y of already added points of X is a triangulation of the space.

  has a Delaunay triangulation in which the star of any given vertex has a constant expected complexity. Hence, the expected complexity of the triangulation is linear in the size of the subsample. The constant of proportionality is bounded by 2 cd 2 , where c is a constant independent of ε and d.

Theorem 4 .

 4 Accordingly, we get two different regimes of the potential simplices in the triangulation. When the circumradius of a potential simplex σ ∈ star(p) is at most 1/4, then the simplex lies in a ball of radius at most 1/2 with center p. By Theorem 4, in this regime the Delaunay complex star(p) embeds in the one-sheeted covering of T d . Therefore, for a fixed set of vertices, there is a unique circumball. When the circumradius is greater than 1/4, the simplex is contained in a ball of radius > 1/2 around p, and therefore star(p) embeds in the 3 d -sheeted covering of T d , i.e. T d 3 . In this case, each vertex has 3 d copies, and so for a given choice of d vertices together with p, one can have (3 d ) d circumballs.

  To bound the expected complexity, we shall consider the probability of existence of potential d-simplices in X , incident to p and having radius in the intervals I k , as k ranges over Z + . Throughout this section, we shall use σ to mean a d-simplex incident to p, with circumcentre c σ and circumradius r σ , and τ to mean the set of vertices of σ \ {p}. To count the number of simplices in star(p) with circumradius in I k , let S p (k) denote the set of possible (d -1)-simplices with vertices in X , such that for every τ ∈ S p (k), the d-simplex σ := τ ∪ {p} has circumradius r σ ∈ I k . Set s p (k) := (S p (k)). Let n k denote the minimum number of points of X in the interior of the circumball of σ, over all τ ∈ S p (k):

Lemma 15 .

 15 triangulations of nice point setsNext, we shall upper bound s p (k) from above. We first state a simple observation. Let σ be a d-simplex incident to p, with circumcentre c σ and circumradiusr σ . Then σ ⊂ B[p, 2r σ ] and B(c σ , r σ ) ⊂ B(p, 2r σ ).Proof. This follows simply from the triangle inequality. For the first statement, we have that for any p ∈ σ, p, p ≤ p, c σ + c σ , p = 2r σ . The second statement follows by replacing the above inequalities with strict inequalities for the points in the open ball B(c σ , r σ ).

/ 4 .

 4 Therefore by Theorem 4, we shall work in the 3 d -sheeted covering of T d . Lemma 19. k>kmax E [Z p (k)] ≤ 5. Proof. From Lemma 3, we have that n = (X ) ≤ 2 -d d d/2 ε -d . Therefore, by Lemma 2, any ball B of radius at least 2 kmax δ ≥ 1/4, has at least (2 kmax δ/ε) d = (1/4ε) d ≥ n 2 d •d d/2 points in its interior, i.e. (intB ∩ X ) ≥ n (2 √ d) d . Here, since 2 k+1 δ > 1/2, we shall use Theorem 4 and work in the 3 d -sheeted covering of T d . The maximum number of d-tuples which can possibly form a Delaunay d-simplex with p, is at most n-1 d ≤ (n -1) d /d!. Since we are working in the 3 d -sheeted covering space, each vertex of a simplex τ ∈ S p (k) can be chosen from one of at most 3 d copies in the covering space. Thus, each simplex in S p (k) yields less than 3 d 2 possible Delaunay spheres in T d . Therefore, the expected number of simplices having radius at least 2 kmax δ, is at most k>kmax

  which completes the proof of Theorem 9.C V I T 2 0 1 6 Polyhedral Surfaces in E 3In this section, we introduce a partition of the sub-sample Y into boundary and interior points, to do a case analysis of the expected number of edges in the Delaunay triangulation Del(Y), depending on whether the end-points of a potential Delaunay edge, are boundary or interior points, and whether they lie on the same facet or on different facets.

  t(Del(Y)) in the Delaunay triangulation of S, is at most e(Del(Y)) -(Y) = e(Del(Y)) -s, where e(Del(Y)) is the number of edges in the Delaunay triangulation. Therefore, it suffices to count the edges of Del(Y). Next, observe that any point x ∈ Y is either a boundary or an interior point, that is Bd S (Y) Int S (Y) = Y. An edge in Del(Y), therefore, can be either between two points in Bd S (Y), or two points in Int S (Y), or between a point in Bd S (Y) and another in Int S (Y). The case of a pair of points in Int S (Y) is further split based on whether the points belong to the same facet of S or different facets. Thus using the above exhaustive case analysis, the proof follows simply by summing the bounds.

)Figure 1 Lemma 26 .

 126 Figure 1 Angle covered by disk of radius 1/2 is = 2α.

Figure 2 For Lemma 28 Lemma 28 .

 22828 Figure 2 For Lemma 28

C V I T 2 0 1 6 23: 18 RIC of Delaunay triangulations of nice point sets Proof of Lemma 21 .

 61821 Let l denote min{Lev(x), Lev(y)}. Observe that if l = 0, then either x or y is a boundary point, and hence we can assume l ≥ 1. Let x = arg min z∈∂F d(z, x), and y = arg min z∈∂F d(z, y), i.e. x is the closest point to x in ∂F , and similarly for y . By the definition of Bd S (Y), observe that d(x, y) ≤ d(x, x ) + d(x , y) ≤ d(x, x ) + d(y, y ) ≤ 2 • 2 l-1 δ.

Figure 3 xFigure 4 xLemma 23 . 21 Y

 342321 Figure 3 x, y ∈ IntS (Y), on different facets F ⊂ P , F ⊂ P

  x ∈ Bd S (Y) and (ii) k y (x) ≤ Lev(y), by applying Construction 33, on the plane P , Z = Bd S (Y), and T = Y ∩ P , and using Proposition 35. By Lemma 36, k y (x) ∈ [0, Lev(y)].

  2 D)) is sketched below. Now we come to the proof of Theorem 11. Proof. To verify that Condition 6 indeed holds in the Euclidean metric case, observe first that the union C p of the simplices in conflict with a new point p is a connected set. Therefore, walking on the adjacency graph of the simplices by rotating around the (d -2)-simplex shared between two adjacent faces on the boundary of C p , is enough to yield the set of new conflicts.

Theorem 43 .

 43 Given a metric d over T d with distortion κ d < ∞, there exists an integer m = m d < (2κ d √ d) d , such that the Delaunay triangulation over (T d , d) embeds in T d m with the Euclidean metric. In particular, if d is of the form d(x, y) = (x -y) M (x -y), x, y ∈ T d , where M ∈ E d×d is a positive definite matrix having condition number at most c M , then m ≤ (2c M √ d) d . Hence, given any ε ∈ [0, 1/4], the statements of Theorems 9 and 11 apply for ε-nets over the metric space (T d , d). For Theorem 43, we use a geometric condition of Caroli-Teillaud [11] (Criterion 3.11) to explicitly bound the multiplicity of the covering space. Proof of Theorem 43. The action of Z d on E d is defined by translation, i.e. for x ∈ E d , g ∈ Z d , gx := g • x = g + x. For a finite point set P ∈ E d , let ∆(Z d P ) denote the largest ball in E d containing no points from Z d P . Let δ((kZ) d ) denote the minimum distance by which a point in E d is translated by (kZ) d . Finally, let π(.) denote the projection map of the covering space T d k on to T d . We shall use the following geometric condition of Caroli and Teillaud [11]. Lemma 44. If ∆(Z d P ) < δ((kZ) d )/2, then for any finite Y ⊃ P , the projection π(Del(Z d Y )) is a triangulation of T d . triangulations of nice point sets Now, observe that in the Euclidean metric, the diameter ∆ . (Z d P ) of the largest ball not containing any point from the set Z d P is at most √ d, with equality holding when (P ) = 1, and that ∆(S ) ≤ ∆(S) for any S ⊇ S, since adding points can only decrease the diameter of the largest empty ball. Therefore, in the metric d, we have that ∆ d (Z d P ) ≤ ∆ . (Z d P ) • By the previously observed bound on ∆ . (Z d P ), we have ∆ d (Z d P ) ≤

2 √

 2 d • κ d < k, since by definition, the distortion κ d satisfies for all x, y ∈ Z d P , d(x, y) ≤ κ d x -y , i.e. κ d ≥ max x,y∈Z d P d(x,y) x-y , as well as x -y ≤ κ d d(x, y), i.e. κ d ≥ min x,y∈Z d P d(x,y) x-y . Since the fundamental domain of T d k contains k d copies of the fundamental domain of T d , we have m ≤ k d , and so the first part of the theorem follows with m ≤ (2 √ dκ d ) d . The second part easily follows from the well-known linear algebraic facts that (a) max x =1 {x M x} = max x =1 { Ax } = σ max (A), and that (b) min x =1 {x M x} = σ max (A -1 ) = σ min (A) where A is such that M = A A and σ max (A), σ min (A) are respectively the largest and the smallest singular values of A.

2 log 2

 2 (1/b) eab . Proof of Lemma 46. The proof follows from elementary calculus. The maximum term is when 2 an = 1/b, i.e. n = log 2 (1/b) a , and evaluates to 2 an exp (-b • 2 an ) = 1 eb , and terms decrease exponentially afterwards. The sum is therefore upper bounded by twice the maximum term, times the number of terms before the maximum, which is the claimed bound. C V I T 2 0 1 6

  + , the flat d-torus T d is the compact quotient group E d /Z d , with addition as the group action. More generally, for k ∈ Z + , the flat torus of length k is T d k

	Lemma 2 (Minimum cover size). Any covering of a ball of radius r in dimension d by balls
	of radius ρ has a number of balls greater than	Ä	r ρ	ä d	.
	Proof. The volume argument gives a lower bound of V d ×r d V d ×ρ d =	Ä	r ρ	ä d	.
	For d ∈ Z
	by disjoint balls of radius ρ/2 has a number of balls smaller than	Ä	3r ρ	ä d	.
	Proof. Consider a maximal set of disjoint balls of radius ρ 2 with center inside the ball B(r)
	of radius r. Then the balls with the same centers and radius ρ cover the ball B(r) (otherwise
	it contradicts the maximality). By a volume argument we get that the number of balls is
	bounded from above by	V d ×(r+ ρ 2 ) V d ×( ρ 2 ) d	d	≤	Ä	3r ρ	ä d	.

Lemma 1 (Maximum packing size). Any packing of the ball of radius r ≥ ρ in dimension d

  Bd F (Y) for some F ∈ S, and x ∈ Int S (Y) is defined similarly. The above bi-partition induces a classification of potential edges, depending on whether the end-points are boundary or interior points. Let E 1 denote the set of edges in Del(Y) of the type {x 1 , x 2 } : x 1 , x 2 ∈ Bd S (Y). Let E 2 denote the set of edges in Del(Y) of the

or x is a boundary point, if k = 0 or if there exists an empty disk (w.r.t. Y) of radius greater than 2 k-1 δ, whose boundary passes through x. x ∈ Int F (Y), or an interior point if and only if x ∈ Y \ Bd F (Y). In general, x ∈ Bd S (Y) if x ∈ type {x, y} : x, y ∈ Int F (Y), for some F ∈ S. Let E 3 denote the set of edges in Del(Y) of the type {x, y} : x, y ∈ Int S (Y), such that x ∈ F , y ∈ F = F . Let E 4 denote the set of edges {x, y} in Del(Y) of the type x ∈ Bd S (Y), y ∈ Int(F ), where F is a facet in S with supporting plane P .

  and k 2 ≤ k 1 , and applying the Decay Lemma 29, we get that

  The rest of the proof follows as before. Coming to our results for Delaunay triangulations of Euclidean d-manifolds and embedded metrics in T d , we need a few definitions first. Bieberbach group G is a discrete group of isometries acting on E d . A d-orbifold E d /G is the compact quotient space (i.e. collection of orbits) of E d acted on by a d-dimensional Bieberbach group G. When the group action is free (i.e. has no fixed points), Given a closed Euclidean d-orbifold M = E d /G, equipped with the Euclidean metric, where G is a d-Bieberbach group, there exists a covering space C M with multiplicity m = m * (G, d), such that the Delaunay complex on M is a triangulation of C M , and the statements of Theorems 9 and 11 apply for ε-nets, for any ε ∈ [0, 1/4].

	Euclidean d-orbifolds
	A d-dimensional

the d-orbifold is a closed Euclidean d-manifold. Every Euclidean d-manifold is the quotient space of some d-Bieberbach group acting on E d

[START_REF] Boileau | Three-dimensional orbifolds and their geometric structures[END_REF]

,

[START_REF] William P Thurston | Three-Dimensional Geometry and Topology[END_REF]

. For Euclidean d-orbifolds, we have: Theorem 41.

  Every Euclidean d-orbifold M has a covering space using a number m M of sheets of a d-hyperparallelepiped Td M , where m M depends only on d, such that the Delaunay triangulation of any point set on M is the projection of the Delaunay complex of the cover of the point set in the covering space.The proof of Theorem 41 is on similar lines as that of Theorem 9, except (i) we work with the hyperparallelepiped Td M , and (ii) we need to take the effect of the multiplicity (i.e. the number m M of sheets of Td M required for Theorem 42 to hold) into account for all simplices.To handle (i), we observe that the volume of balls will change as the hyperparallelepiped is no longer a hypercube. Thus, a factor of the volume of the unit hyperparallelepiped Td

M , will come into the estimates in Lemma 5. To handle the effect of multiplicity, we introduce an extra multiplicative factor of m d M in the bound of the number of possible d-simplices with any fixed set of points (compared to Lemma 19

). Additionally, we take into account that the number of distinct points inside a potential simplex is at least a 1/m M -fraction of the number guaranteed by Lemma 13. This gives a worse bound for the expected complexity of the star than in Theorem 9, but still a constant.

  For the flat torus T d k , min x,g x -gx = k. Therefore, in the metric d, the condition of

		δ d ((kZ) d ) =	min x∈G, g∈((kZ) d ) *	d(x, gx) =	min x∈G, g∈((kZ) d ) *	d(x, gx) x -gx	• x -gx .
	Lemma 44 is satisfied if
						max x,y∈Z d P	d(x, y) x -y	•	√	d <	1 2	Å x∈P, g∈((kZ) d ) * min	d(x, gx) x -gx	• x -gx	ã	, or,
	2 √	d • max x,y∈Z d P	d(x, y) x -y	•	max

d , x ∈P, g∈((kZ) d ) * x -gx d(x , gx ) < k, which is true if 2 √ d • max x,y∈Z d P d(x, y) x -y • min x ,y ∈Z d P d(x , y ) x -y < k, or,

. This work is supported by the European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions).

Construction 31 ). Let P and P denote the supporting planes of the facets F and F respectively. Let P B be the bisector plane of P and P . We denote by x ∈ P , the reflection of x ∈ P with respect to P B , and similarly by y ∈ P , the reflection of y ∈ P . Let B = B xyx y be the smallest ball in E 3 passing through x, y, x , y , having intersections D 1 = B ∩ P and D 2 = B ∩ P with P and P respectively.

Attali and Boissonnat observed that

Proposition 32 ). Any ball in E 3 having x and y on its boundary,

Therefore, if there exists a ball B ∈ E 3 such that x, y ∈ ∂B, and int(B)

Observe that, as in Case II, we have x ∈ D(y, 2 Lev(y) δ), since otherwise y ∈ Bd S (Y). (Note that our definition of boundary points allows us to ignore the fact that x is not necessarily a point in X .) Further, the set {x ∈ D(y,

The rest of the analysis for the fixed facet F , therefore follows as in

Before proving Lemma 23, we briefly describe a construction, which will be central to our analysis.

Construction 33 ). Let P be a plane and Z be a finite set of points.

To each point x ∈ Z, assign the region V (x) = V x (Z) ⊂ P of points y ∈ P such that the sphere tangent to P at y and passing through x encloses no point of Z.

We summarize some conclusions of Attali-Boissonnat regarding the construction. The proofs of these propositions can be found in [START_REF] Attali | A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces[END_REF].

Proposition 34.(i) V is a partition of P .

(ii) For each x ∈ Z, V (x) is an intersection of regions that are either disks or complements of disks.

(iii) The total length of the boundary curves in V is equal to the total length of the convex boundaries.

Proof. The proofs are (i) and (ii) are easy.

(iii) Consider a point x ∈ Z, and let V (x) be the region corresponding to x in V. By Proposition 34 (ii), V (x) = (∩ D∈Dx D) (∩ D∈Cx D), where D x is a set of disks and C x is a set of complements of disks in the plane P . Let y ∈ ∂V (x). Then if y ∈ ∩ D∈Dx D, then there exists D 1 ∈ D x , such that y ∈ ∂D 1 , and so y is part of a convex segment in ∂V (x).

Otherwise, there exists D2 ∈ C x , such that y ∈ ∂ D2 . In this case, let V (z), z ∈ Z, denote the region such that y ∈ ∂V (z). Then D 2 ⊃ V (z), and therefore y belongs to a convex segment in ∂V (z).

Thus, every point y ∈ ∂V (x) is convex either for V (x) or for a neighbouring region of V (x), and so the total length of the convex boundary curves in V gives the total length of all the boundary curves. (ii) With probability at least a constant, there exists a ball of radius Ω(ε log k) with no points in S.

Sketch of Proof.

The following balls-and-bins and coupon-collector arguments which can be shown to prove this: