Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

A weak characterisation of the Delaunay triangulation

We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional (strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented by a finite point sample.      

Conforming Delaunay triangulations in 3D

We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC. The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem.     

Stabbing Delaunay Tetrahedralizations

A Delaunay tetrahedralization of $n$ vertices is exhibited for which a straight line can pass through the interiors of $\Theta(n^2)$ tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than $O(n)$ tetrahedra. The construction generalizes to higher dimensions: in $d$ dimensions, a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$ Delaunay $d$-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a $d$-dimensional $n$-vertex polytope can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets. This last result was first demonstrated by Amenta and Ziegler, but the construction given here is simpler and more intuitive.     

Estimating a Nonstationary Spatial Structure Using Simulated Annealing

During the past decade, a useful model for nonstationary random fields has been developed. This consists of reducing the random field of interest to isotropy via a bijective bi-continuous deformation of the index space. Then the problem consists of estimating this space deformation together with the isotropic correlation in the deformed index space. We propose to estimate both this space deformation and this isotropic correlation using a constrained continuous version of the simulated annealing for a Metropolis-Hastings dynamic. This method provides a nonparametric estimation of the deformation which has the required property to be bijective; so far, the previous nonparametric methods do not guarantee this property. We illustrate our work with two examples, one concerning a precipitation dataset. We also give one idea of how spatial prediction should proceed in the new coordinate space.     

Smooth surface reconstruction via natural neighbour interpolation of distance functions

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates non-uniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in .     

Delaunay refinement algorithms for triangular mesh generation

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles.

Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin[( , where φ60°is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest.

Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.     

Witness sets of projections

Elimination is a basic algebraic operation which geometrically corresponds to projections. This article describes using the numerical algebraic geometric concept of witness sets to compute the projection of an algebraic set. The ideas described in this article apply to computing the image of an algebraic set under any linear map.     

Manifold Reconstruction Using Tangential Delaunay Complexes

We give a provably correct algorithm to reconstruct a k-dimensional smooth manifold embedded in d-dimensional Euclidean space. The input to our algorithm is a point sample coming from an unknown manifold. Our approach is based on two main ideas: the notion of tangential Delaunay complex defined in Boissonnat and Flötotto (Comput. Aided Des. 36:161–174, 2004), Flötotto (A coordinate system associated to a point cloud issued from a manifold: definition, properties and applications. Ph.D. thesis, 2003), Freedman (IEEE Trans. Pattern Anal. Mach. Intell. 24(10), 2002), and the technique of sliver removal by weighting the sample points (Cheng et al. in J. ACM 47:883–904, 2000). Differently from previous methods, we do not construct any subdivision of the d-dimensional ambient space. As a result, the running time of our algorithm depends only linearly on the extrinsic dimension d while it depends quadratically on the size of the input sample, and exponentially on the intrinsic dimension k. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity depends linearly on the ambient dimension. We also prove that for a dense enough sample the output of our algorithm is isotopic to the manifold and a close geometric approximation of the manifold.     

Triangulations in CGAL

This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library .     

Spanners of additively weighted point sets

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs (p,r) where p is a point in the plane and r is a real number. The distance between two points (pi,ri) and (pj,rj) is defined as |pipj|−ri−rj. We show that in the case where all ri are positive numbers and |pipj|?ri+rj for all i, j (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a (1+?)-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has a spanning ratio bounded by a constant. The straight-line embedding of the Additively Weighted Delaunay graph may not be a plane graph. Given the Additively Weighted Delaunay graph, we show how to compute a plane straight-line embedding that also has a spanning ratio bounded by a constant in time.     

The flow complex: A data structure for geometric modeling

We study a special case of the critical point (Morse) theory of distance functions namely, the gradient flow associated with the distance function to a finite point set in . The fixed points of this flow are exactly the critical points of the distance function. Our main result is a mathematical characterization and algorithms to compute the stable manifolds, i.e., the inflow regions, of the fixed points. It turns out that the stable manifolds form a polyhedral complex that shares many properties with the Delaunay triangulation of the same point set. We call the latter complex the flow complex of the point set. The flow complex is suited for geometric modeling tasks like surface reconstruction.     

A framework for advancing front techniques of finite element mesh generation

Advancing front techniques are a family of methods for finite element mesh generation that are particularly effective in dealing with complicated boundary geometries. In the first part of this paper, conditions are presented which ensure that any planar aft algorithm that meets these conditions terminates in a finite number of steps with a valid triangulation of the input domain. These conditions are described by specifying a framework of subtasks that can accommodate many aft methods and by prescribing the minimal requirements on each subtask that ensure correctness of an algorithm that conforms to the framework.An important efficiency factor in implementing an aft is the data structure used to represent the unmeshed regions during the execution of the algorithm. In the second part of the paper, we discuss the use of the constrained Delaunay triangulation as an efficient abstract data structure for the unmeshed regions. We indicate how the correctness conditions of the first part of the paper can be met using this representation. In this case, we also discuss the additional requirements on the framework which ensure that the generated mesh is a constrained Delaunay triangulation for the original boundary.The first author has been supported by CERFACS, Toulouse, France. Support was provided to the second author by the Natural Sciences and Engineering Research Council of Canada, and by the Information Technology Research Centre of Ontario.     

Fast reconstruction of Delaunay triangulations

We present a new linear time algorithm to compute a good order for the point set of a Delaunay triangulation in the plane. Such a good order makes reconstruction in linear time with a simple algorithm possible. Similarly to the algorithm of Snoeyink and van Kreveld [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471], our algorithm constructs such orders in O(logn) phases by repeatedly removing a constant fraction of vertices from the current triangulation. Compared to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] we improve the guarantee on the number of removed vertices in each such phase. If we restrict the degree of the points (at the time they are removed) to 6, our algorithm removes at least 1/3 of the points while the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471] gives a guarantee of 1/10. We achieve this improvement by removing the points sequentially using a breadth first search (BFS) based procedure that—in contrast to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471]—does not (necessarily) remove an independent set.

Besides speeding up the algorithm, removing more points in a single phase has the advantage that two consecutive points in the computed order are usually closer to each other. For this reason, we believe that our approach is better suited for vertex coordinate compression.

We implemented prototypes of both algorithms and compared their running time on point sets uniformly distributed in the unit cube. Our algorithm is slightly faster. To compare the vertex coordinate compression capabilities of both algorithms we round the resulting sequences of vertex coordinates to 16-bit integers and compress them with a simple variable length code. Our algorithm achieves about 14% better vertex data compression than the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459–471].     

On the stretch factor of Delaunay triangulations of points in convex position

Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance |pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33.     

Efficiently navigating a random Delaunay triangulation

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant spanning ratio (w.r.t the Euclidean distance) which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q; cone walk applied to z and q will access at most sites with complexity with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is ‐memoryless with high probability for any pair of start and query point in the domain, for any positive ξ. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 95–136, 2016     

2D Centroidal Voronoi Tessellations with Constraints

<正>We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.