Arc Triangulations

O. Aichholzer, W. Aigner, F. Aurenhammer, K. Dobiášová, and B. Jüttler

Abstract:

The quality of a triangulation is, in many practical applications, influenced by the angles of its triangles. In the straight line case, angle optimization is not possible beyond the Delaunay triangulation. We propose and study the concept of circular arc triangulations, a simple and effective alternative that offers flexibility for additionally enlarging small angles. We show that angle optimization and related questions lead to linear programming problems, and we define unique flips in arc triangulations. Moreover, applications of certain classes of arc triangulations in the areas of finite element methods and graph drawing are sketched.

Reference: O. Aichholzer, W. Aigner, F. Aurenhammer, K. Dobiášová, and B. Jüttler. Arc triangulations. In Proc. $26^{th}$ European Workshop on Computational Geometry EuroCG '10, pages 17-20, Dortmund, Germany, 2010.