๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An optimal algorithm for realizing a Delaunay triangulation

โœ Scribed by Timothy Lambert

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
456 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 algorithm is generating test data for algorithms that process convex polygons. ($ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

An efficient sweep-line Delaunay triangu
An efficient sweep-line Delaunay triangulation algorithm
โœ Borut ลฝalik ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 587 KB

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, w

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

A generalized Delaunay triangulation alg
A generalized Delaunay triangulation algorithm with adaptive grid size control
โœ Kumar, K. S. Vasanth ;Babu, A. V. Ramesh ;Seetharamu, K. N. ;Sundararajan, T. ;N ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 191 KB ๐Ÿ‘ 2 views

A generalized unstructured mesh generation procedure using Delaunay triangulation has been developed for adaptive ยฎnite element applications. The main features of the method include: (i) a fast and ecient initial triangulation; (ii) interior node insertion with good control over the grid size and as