|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/3091
|
| Title: | Delaunay edge flips in dense surface triangulations |
| Authors: | Cheng, Siu-Wing
Dey, Tamal K. |
| Keywords: | Edge flip
Triangulations
Delaunay |
| Issue Date: | 12-Dec-2007 |
| 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 triangulation 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. |
| URI: | http://hdl.handle.net/1783.1/3091 |
| Appears in Collections: | CSE Preprints
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| flip.pdf | | 1650Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
