Optimal triangulation problems

Abstract

This paper surveys some recent solutions to triangulation problems in 2D plane and surface. In particular, it focuses on three efficient and practical schemes in computing optimal triangulations useful in engineering and scientific computations, such as finite element analysis and surface interpolation. The edge-insertion paradigm can compute for a set of n vertices, with or without constraining edges, a minmax angle and a max-min height triangulation in O(n2 log n) time and O(n) storage, and a min-max slope and a min-max eccentricity triangulation in O(n3) time and O(n2) storage. The subgraph scheme can compute a min-max length triangulation for a set of n vertices in O(n2) lime and storage. Length refers to edge length and is measured by some normed metric such as the Euclidean or any other ℓp metric. Additionally, the scheme provides some insight to the minimum weight triangulation problem. The wall scheme can compute for a given set of n vertices and m constraining edges, a conforming Delaunay triangulation of O(m2n) vertices. Additionally, an extension of the wall scheme can refine a triangulation of size O(n) to a quality triangulation of size O(n2) that has no angle measuring more than 11/15π.