Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstructing Intrinsic Delaunay Triangulations of Submanifolds
461
0
0.0
(
0
)
Added by
Ramsay Dyer
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Jean-Daniel Boissonnat
Ask ChatGPT about the research
No Arabic abstract
We describe an algorithm to construct an intrinsic Delaunay triangulation of a smooth closed submanifold of Euclidean space. Using results established in a companion paper on the stability of Delaunay triangulations on $delta$-generic point sets, we establish sampling criteria which ensure that the intrinsic Delaunay complex coincides with the restricted Delaunay complex and also with the recently introduced tangential Delaunay complex. The algorithm generates a point set that meets the required criteria while the tangential complex is being constructed. In this way the computation of geodesic distances is avoided, the runtime is only linearly dependent on the ambient dimension, and the Delaunay complexes are guaranteed to be triangulations of the manifold.
rate research
Read More
We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of $delta$-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.
Delaunay flip is an elegant, simple tool to convert a triangulation of a point set to its Delaunay triangulation. The technique has been researched extensively for full dimensional triangulations of point sets. However, an important case of triangulations which are not full dimensional is surface triangulations in three dimensions. In this paper we address the question of converting a surface triangulation to a subcomplex of the Delaunay triangulation with edge flips. We show that the surface triangulations which closely approximate a smooth surface with uniform density can be transformed to a Delaunay triangulation with a simple edge flip algorithm. The condition on uniformity becomes less stringent with increasing density of the triangulation. If the condition is dropped completely, the flip algorithm still terminates although the output surface triangulation becomes almost Delaunay instead of exactly Delaunay.
Delaunay has shown that the Delaunay complex of a finite set of points $P$ of Euclidean space $mathbb{R}^m$ triangulates the convex hull of $P$, provided that $P$ satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunays genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on $P$ are required. A natural one is to assume that $P$ is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.
We study densities of functionals over uniformly bounded triangulations of a Delaunay set of vertices, and prove that the minimum is attained for the Delaunay triangulation if this is the case for finite sets.
We study epidemic outbreaks on random Delaunay triangulations by applying Asynchronous SIR (susceptible-infected-removed) model kinetic Monte Carlo dynamics coupled to lattices extracted from the triangulations. In order to investigate the critical behavior of the model, we obtain the cluster size distribution by using Newman-Ziff algorithm, allowing to simulate random inhomogeneous lattices and measure any desired percolation observable. We numerically calculate the order parameter, defined as the wrapping cluster density, the mean cluster size, and Binder cumulant ratio defined for percolation in order to estimate the epidemic threshold. Our findings suggest that the system falls into two-dimensional dynamic percolation universality class and the quenched random disorder is irrelevant, in agreement with results for classical percolation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
