Project Topics
Get Complete Project Material File(s) Now! »
Medial axis and contact types
In this paragraph, we extend the notion of contact points and medial axis, aforementioned for planar
curves. We assume that S is a generic smooth surface and show the properties that the genericity induces on the medial axis of S. By smooth we actually mean that S is not only C1 but also analytic, otherwise the surface could have a very complex medial axis [CCM97]. Medial sphere and symmetrical points We call a medial sphere of S at p, or medial sphere of p, the boundary of a maximal open ball B with p on its boundary such that B \ S = ;. We recall that for a point p on a planar curve, a symmetrical point p of p is a point of the curve such that there exists a medial circle passing through p and p. This notion can be extended to surfaces. We say that two different points are symmetrical on S if their exists a medial sphere passing through those two points.
For a given orientation, we can talk about the medial sphere (p) of a point p, that is the one centered in the direction ~n(p) . We denote by c(p) its center, and by r(p) its radius, respectively called medial center and medial radius of p. When it is clear that they depend on p, we will simple write , c or r. We say that p 2 S is a symmetrical point of p only if the medial sphere of p passes also through p. In other words, the symmetrical points of p depends on the chosen orientation.
Taking into account the notion of medial radius, we can give another definition of Z: Z is the set of points p such that 1(p) = r(p). Indeed, when two symmetrical points approach each other, their medial sphere tends to be osculating. If the surface is closed, then we can consider the minimal medial radius, also called reach in [BLW19], and denoted rch: rch := min p2S (r(p)).
Counting the edges of a planar graph
The main purpose of the thesis is to compute the number of edges of a given graph according to its number of vertices. For a set A, we will denote by ]A the number of elements in A. For a graph G = (V;E), ]G is also called size, or combinatorial complexity, of the graph. ]G corresponds to ]E + ]V , so we are interested in computing ]E with respect to ]V . The Euler’s formula [Eul58] gives a relation between the numbers ]V , ]E, and ]F in a connected plane graph:
Theorem 2.1 (Euler’s formula). Let V , E, and F be respectively the set of vertices, edges and faces of a connected plane graph, then: ]V ]E + ]F = 2.
If a plane graph is maximal, then all of its faces are triangles, and even the outer face has 3 edges. Thus we can claim that each edge is the boundary of two distinct faces, and that each face is bounded by exactly 3 edges. Knowing that, we can proceed to the counting of incidences (e; f) where e is an edge of the face f. Since for each edge, there are 2 faces, the number of such incidences is 2]E. On the other hand, since all faces are triangles we can say that the number of incidences is 3]F . Thus in a maximal planar graph, we have the following relation: 2]E = 3]F.
The 2D-Delaunay triangulation
If the vertices are actually geometric points in Rd, for any d 1, we can consider graphs that depend on the relative position of the points. One example of such graphs in R2 is the graph induced by the Delaunay triangulation [Del34].
Formally, a Delaunay triangulation of a set of points is a simplicial complex, i.e. a set of vertices, edges, triangles, and simplices of higher dimension if necessary, such that any sub-simplex of a simplex (any edge of a triangle for instance) is in the simplicial complex, and the non-empty intersection of two simplices is a sub-simplex of both.
In dimension 2, for a set of vertices V in general position (no three vertices aligned, no four vertices cocyclic), the Delaunay triangulation, denoted Del(V ), of V is the unique simplicial complex (V;E; F) in which (p; q; r) is a triangle of F if and only if the circle C circumscribing p, q and r has no points of V in its interior. In that case, we say that C is empty. It is equivalent to say that (p; q) is an edge of E if and only if there exists an empty circle C passing through p and q. Note that one of the definitions involves three points and one circle, while the other involves two points and a whole pencil of circles. This will make an important difference later.
The Delaunay triangulation of V induces the graph (V;E) that is a plane graph whose all faces are triangles except for the outer face (see Figure 2.3). We will often refers to the Delaunay triangulation or to its induced graph without distinction.
To have a complete information on the Delaunay triangulation, it requires then to know not only the set of points and edges, but also the set of faces. Thus the combinatorial complexity of a 2D triangulation is then given by the sum ]V +]E +]F . We denote it by ] Del(V ), and call it more simply the size of the triangulation. In 2D, since the Delaunay triangulation is planar, the Euler formula is enough to evaluate ] Del(V ) for any set of points V , indeed we have: ] Del(V ) = (]V ).
Expected size of the dD-Delaunay triangulation of a uniform set of points
In his paper “Higher-dimensional Voronoi diagrams in linear expected time” [Dwy91], Dwyer proved, in 1991, that when n points are uniformly distributed in a unit d-ball in Rd, the expected size of the Delaunay triangulation is (n):
Theorem 4.1 (Dwyer, 1991). Let X be a set of n sites drawn independently from the uniform distribution on the interior of the unit d-ball. Then the expected number of simplices of the dual of the Voronoi diagram of X, is (n) for fixed d as n ! 1.
Actually, the result in the paper is more precise since the hidden constant in the (n) is given. Even if we did not mention it in the background, the Voronoi diagram is a fundamental object of computational geometry. It is the dual of the Delaunay triangulation, defined for a set X of points, as the set of convex regions fx 2 Rd; dist(x; p) dist(x; q) 8q 2 Xnfpgg for all p 2 X. Thus, the number of edges issue from p in the Delaunay triangulation is the number of faces of the region of p in the Voronoi diagram (see Figure 4.1).
In the first section of the paper, Dwyer establishes a general formula that expresses the probability Pn that a d-simplex is in the triangulation. Thus, if Sn expresses the number of simplices of Del(X), then E [Sn] = n d + 1 Pn.
Analysis of the 3D-Delaunay triangulation of points on a polyhedral surface
In [Dwy91], the points were distributed randomly. The choice of using a random distribution has various reasons, such as being easier to simulate. Indeed, it corresponds to a sample naturally homogeneous (the expected number of points in a region depends directly on the volume of the region), the expressions used for computation are derived from probabilistic theories, we can obtain exact values and not only results up to a constant. But we could have consider other samples, not necessarily random.
For practical problems, like surface reconstruction, we can be interested in distributing the points on a subset of the ambient space with a smaller dimension. The next papers that we present deal with the case where points are distributed on surfaces.
There are various way to distribute such points. As in [Dwy91], we can use a random sample, either
uniform or Poisson. Among the advantages of random process, we can note that they almost surely exclude pathological position of points. We can also use a deterministic sample. In this case, we have to specify conditions so the sample is sufficiently good. To study the size of the Delaunay triangulation, we want the number of points distributed in a region to be directly related with the area of such a region. A natural idea for a deterministic sample can be to distribute the points on a grid, but this is not a very good idea with the Delaunay triangulation since some points may be co-spherical. Another condition can be: any ball of a given radius contains at least one point of the sample, for instance. There can be different kinds of such deterministic samples. We all gather them under the name nice samples.
Table of contents :
I Presentation of general notions
1 Geometry
1.1 Geometry of plane curves
1.1.1 The notion of curvature
1.1.2 The medial axis of a curve
1.2 Geometry of surfaces
1.2.1 Basic notions on surfaces
1.2.2 Analytic description of a surface
1.3 Generic surface
1.3.1 Maxima of curvature
1.3.2 Medial axis and contact types
1.3.3 Summary of the cases
2 Combinatorics
2.1 Graph theory
2.1.1 Generalities on graphs
2.1.2 Counting the edges of a planar graph
2.2 The Delaunay triangulation
2.2.1 The 2D-Delaunay triangulation
2.2.2 In three dimensions (and higher)
3 Probabilities
3.1 Poisson point process
3.2 Slivnyak-Mecke’s theorem
4 State of the art
4.1 Expected size of the dD-Delaunay triangulation of a uniform set of points
4.2 Analysis of the 3D-Delaunay triangulation of points on a polyhedral surface
4.2.1 Probabilistic analysis
4.2.2 Deterministic analysis
4.2.3 On polyhedral surfaces of any dimension
4.3 Evaluating the size of the Delaunay triangulation with respect to the spread of the points
4.4 Another probabilistic approach
4.5 Deterministic nice sample on generic surfaces
5 A Poisson sample on a surface is a good sample
5.1 Notation, definitions, previous results
5.2 Is a Poisson sample a good sample?
II Stochastic analysis of empty region graphs
6 A sub-graph and a super-graph of the 2D-Delaunay triangulation
6.1 The Gabriel and half-moon graphs
7 General method
7.1 Empty region graphs
7.2 Combination and Partition lemmas
7.3 Alternative proof of the linear complexity of the Delaunay triangulation
7.4 Formalized method
7.5 Expected degree in some empty singleton-region graphs
8 Empty axis-aligned ellipse graphs
8.1 Some features with axis-aligned ellipses
8.2 Empty axis-aligned ellipse graph
8.2.1 Upper bound on the expected degree
8.2.2 Lower bound on the expected degree
8.3 Ellipses with bounded aspect ratio, the rhombus graph
8.3.1 An upper bound on the expected degree
8.3.2 A lower bound on the expected degree
8.4 On empty axis-aligned ellipse graphs with a single aspect ratio
9 On the probability of the existence of far neighbors
9.1 In the Delaunay triangulation
9.2 In the empty axis-aligned graph with bounded aspect ratio
10 Analysis of two additional empty region graphs
10.1 Empty ellipse graph with bounded aspect ratio
10.2 Empty 4/2-ball graph
11 On nearest-neighbor-like graphs, a way to compute some integrals
11.1 The nearest-neighbor graph
11.2 Formalization
11.3 Application of nearest-neighbor-like graphs
III 3D-Delaunay triangulation for two specific surfaces
12 Delaunay triangulation of a Poisson process on a cylinder
12.1 The right circular cylinder
12.2 Description of the fundamental regions on the cylinder
12.3 Proof of the graph inclusion
12.4 Computation of an upper bound on E [] Del(X)]
12.5 A lower bound on E [] Del(X)]
12.6 Conjecture on two classes of surface
13 Delaunay triangulation of a Poisson process on an oblate spheroid
13.1 The oblate spheroid
13.1.1 Some generalities on the oblate spheroid
13.2 Overview of the proof
13.3 On the probability of existence of neighbors far from the medial sphere
13.4 Expected number of close neighbors
13.4.1 General scheme
13.4.2 Description of the regions of F1 on the spheroid
13.4.3 Choice of specific spheres for q on the side of p with respect to PMed
13.4.4 Proof of the graph inclusion
13.4.5 When q is on the side of p with respect to PMed
13.4.6 Computation of an upper bound on the expected number of close neighbors
13.4.7 On some geometric quantities close to Z
13.4.8 On the probability of existence Delaunay neighbors outside CN(p)
13.5 Expected degree of a point close to Z
13.5.1 Description of fundamental regions on the spheroid
13.5.2 Choice of specific spheres
13.5.3 Proof of the graphs inclusion
13.5.4 Computation of an upper bound on the expected degree
13.5.5 On the probability of existence Delaunay neighbors outside MRN(p)
14 Experimental results
14.1 Simulation
14.2 Experimental results
IV Expected size of the 3D-Delaunay triangulation of a Poisson point process distributed on a generic surface
15 Generic surfaces
15.1 What is generic or not in an oblate spheroid
15.1.1 Common points between an oblate spheroid and a generic surface
15.1.2 Differences between an oblate spheroid and a generic surface
15.2 Sketch of proof
15.2.1 Decomposition of the generic surface
15.2.2 Approach of the proof
16 Expected local degree of a point
16.1 Local degree of a point on the convex hull and a little beyond
16.1.1 Choice of the specific spheres
16.1.2 Proof of the graph inclusion
16.1.3 Computation of the expected local degree
16.2 Local degree of a point far from the convex hull and from Z
16.2.1 Choice of the specific spheres
16.2.2 Proof of the graph inclusion
16.2.3 Computation of the expected degree
16.3 Local degree of a point close to Z or Y
16.3.1 On the position of p and the value 1 1(p)r(p)
16.3.2 Local degree of a point at distance hp from Z
16.3.3 Local degree of a point close to Y
Bibliography
