Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Katerina Čech
Dobiášová, Bert Jüttler, and Günter Rote:
Triangulations with circular arcs
In "Graph Drawing". GD 2011, Proceedings of the 19th International
Symposium on Graph Drawing, Eindhoven, September 2011, Revised Selected Papers.
Editors: Marc van Kreveld and Bettina Speckmann, Lecture Notes in Computer
Science, 7034, Springer-Verlag, 2012, pp. 296–307. doi:10.1007/978-3-642-25878-7_29
Journal of Graph Algorithms and
Applications 19, no. 1 (2015), 43–65.
An important objective in the choice of a triangulation of a point set is
that the smallest angle becomes as large as possible. In the straight-line
case, it is known that the Delaunay triangulation is optimal in this respect.
We propose and study the concept of a circular arc triangulation, which
offers additional flexibility for enlarging small angles. We show that angle
optimization and related questions lead to a linear programming problem that
can be solved by simple graph-theoretic methods.
Last update: January 27, 2015.