Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Katerina Čech Dobiášová, Bert Jüttler, and Günter Rote:

Triangulations with circular arcs

  1. 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
  2. Journal of Graph Algorithms and Applications 19, no. 1 (2015), 43–65. doi:10.7155/jgaa.00346

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.

  slides of the talk   pdf file (gzipped)
other papers about this subject
Last update: January 27, 2015.