Delaunay Triangular Meshes in Convex Polygons

SIAM Journal on Scientific and Statistical ComputingPublished 1 April 1986

Barry Joe

Citations58

TL;DR

An algorithm for producing a triangular mesh in a convex polygon is presented and the expected time complexity is shown to be linear in the number of triangles in the mesh.

Abstract

An algorithm for producing a triangular mesh in a convex polygon is presented. It is used in a method for the finite element triangulation of a complex polygonal region of the plane in which the region is decomposed into convex polygons. The interior vertices of the mesh are chosen to be on a quasi-uniform grid, different mesh spacings are specified for the edges of the polygon, and the mesh is a Delaunay triangulation. The correctness of the algorithm is proved and the expected time complexity is shown to be linear in the number of triangles in the mesh.

Keywords

Computer ScienceBusiness, Management and AccountingEngineering

Closest-point problems

1,062 Citations1975Michael Ian Shamos, Dan Hoey

The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.

Elsevier eBooksSoftware for C1 Surface Interpolation

733 Citations1977C. L. Lawson

This chapter discusses algorithm and underlying theory of software for C1 surface interpolation, an interpolation algorithm that is interfaced with algorithms for contour plotting or surface perspective plotting for data given on a rectangular grid.

The Computer JournalLocally equiangular triangulations

413 Citations1978Robin Sibson

View PDF

International Journal for Numerical Methods in EngineeringAutomatic triangulation of arbitrary planar domains for the finite element method

264 Citations1974James C. Cavendish

A new algorithm for the semi-automatic triangulation of arbitrary, multiply connected planar domains based upon a modification of a finite element mesh genration algorithm recently developed is described.

Journal of the ACMAn Optimal Algorithm for Finding the Kernel of a Polygon

157 Citations1979D. T. Lee, F. P. Preparata

It is shown that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs m time O(n) and is therefore optimal.

View PDF

International Journal for Numerical Methods in EngineeringAutomatic generation of triangular grid: I—subdivision of a general polygon into convex subregions. II—triangulation of convex polygons

69 Citations1976Alex Bykat

International Journal for Numerical Methods in EngineeringModification to the Suhara‐Fukuda method of network generation

58 Citations1978Rachael Shaw, R. G. Pitchen

Improvements to the Suhara-Fukuda method for generating a triangular finite element network are described, based on the use of a node generation procedure which distributes nodes is a regular pattern across the network area and is sufficiently flexible to permit any variation in element density.

SIAM Journal on Scientific and Statistical ComputingA Two-Dimensional Mesh Verification Algorithm

7 Citations1981R. B. Simpson

For a particular format of lists, a set of conditions is given which is proven to be sufficient to guarantee such a “tiling” of some planar region without overlap or gaps.