Premium quality Steiner triangulations

A complex geometric domain is required to be partitioned into a small set of simple and high-quality geometric elements for accurate numerical analysis. Given a two-dimensional input domain, we consider its quality triangulations as the discretization of the domain into non-overlapping triangles while each satisfies certain quality constraints. Related to this, many researchers studied two major problems. The first one is to generate triangulations with a lower bound on small angles, while the second is to generate triangulations with an upper bound on large angles. An upper bound on large angles does not imply a non-trivial lower bound on small angles. Here, we propose novel ideas to generate premium quality triangulations with significantly better simultaneous small and large angle bounds than the bounds provided by the existing methods in practice.;Delaunay refinement is a well-known triangulation technique, which generates size-optimal good-quality Delaunay triangulations. Delaunay refinement algorithms aim to compute triangulations that have all angles at least alpha. However, in practice, these algorithms usually work for alpha ≤ 34° and fail to terminate for larger constraint angles.;We describe two novel ideas to improve the performance of Delaunay refinement algorithms. The first idea is an effective use of the Voronoi diagram and unifies previously suggested point insertion schemes together with a new strategy. The second idea which is, integration of a local relocation strategy into the refinement process, leads to a strategy that has significantly better performance than performing these two tasks independently. In addition to providing the same theoretical guarantees as the previous algorithms, our approach generates smaller triangulations and generally terminates for constraint angles up to 42°. We also extend our ideas to accommodate simultaneous small and large angle constraints. Experimental study shows that our method works for small angles as high as 41°, and large angles as low as 81°. Hence, we provide a substantial improvement over the existing results, especially for applications where acute or non-obtuse triangulations without small angles are desired. Employing these ideas provide the first software for computing premium quality triangulations for complex geometric domains.