Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Triangulations with Circular Arcs
Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Kateřina Čech Dobiášová, Bert Jüttler, and Günter Rote
Vol. 19, no. 1, pp. 43-65, 2015. Regular paper.
Abstract An important objective in the choice of a triangulation of a given point set is that the smallest angle becomes as large as possible. When triangulation edges are straight line segments, it is known that the Delaunay triangulation is the optimal solution. We propose and study the concept of a circular arc triangulation, 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 that can be formulated as simple graph-theoretic problems, and we define flipping operations in arc triangles. Moreover, special classes of arc triangulations are considered, for applications in finite element methods and graph drawing.
Submitted: September 2012.
Accepted: January 2015.
Final: January 2015.
Published: January 2015.
Communicated by Prosenjit K. Bose