Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDelaunay Edge Flips in Dense Surface Triangulations
236
0
0.0
(
0
)
Added by
Tamal Dey
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n log c + h log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
