Delaunay Edge Flips in Dense Surface Triangulations

Details Delaunay Edge Flips in Dense Surface Triangulations Delaunay Edge Flips in Dense Surface Triangulations

2007-12-12

arxiv.org/abs/0712.1959v1

Computer Science

Computational Geometry

This paper is prelude to "Maintaining Deforming Surface Meshes" by Cheng-Dey in SODA 2008

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Delaunay Edge Flips in Dense Surface Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Delaunay Edge Flips in Dense Surface Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Delaunay Edge Flips in Dense Surface Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661646