𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An efficient sweep-line Delaunay triangulation algorithm

✍ Scribed by Borut Žalik

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
587 KB
Volume
37
Category
Article
ISSN
0010-4485

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It is based on a sweep-line paradigm, which is combined with a local optimization criterion-a characteristic of incremental insertion algorithms. The sweep-line status is represented by a so-called advancing front, which is implemented as a hash-table. Heuristics have been introduced to prevent the construction of tiny triangles, which would probably be legalized. This algorithm has been compared with other popular Delaunay algorithms and it is the fastest algorithm among them. In addition, this algorithm does not use a lot of memory for supporting data structure, it is easy to understand and simple to implement.

📜 SIMILAR VOLUMES

An optimal algorithm for realizing a Del
An optimal algorithm for realizing a Delaunay triangulation
✍ Timothy Lambert 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 456 KB

## Dillencourt ( 1990) gives a constructive proof for the realizability as a Delaunay triangulation of any triangulation of the interior of a simple polygon. A naive implementation of the construction will take 0( n\*) time. I give a simple O(n) algorithm for this problem. An application of this a

An Advancing Front Delaunay Triangulatio
An Advancing Front Delaunay Triangulation Algorithm Designed for Robustness
✍ Dimitri J. Mavriplis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 922 KB

A new algorithm is described for generating an unstructured mesh about an arbitrary two-dimensional configuration. Mesh points are generated automatically by the algorithm in a manner which ensures a smooth variation of elements, and the resulting triangulation constitutes the Delaunay triangulation