@inproceedings{f4fb0609d5b44ef790f3b80d6b49bd49,

title = "Optimal triangulation with steiner points",

abstract = "There are many ways to triangulate a simple n-gon; for certain optimization criteria such as maximization of the smallest internal angle it is known how to efficiently compute the best triangulation with respect to this criterion. In this paper we consider a natural extension of this problem: Given a simple polygon P and one Steiner point p in its interior, determine the optimal location of p and a triangulation of P and p which is best amongst all triangulations and placements of p. We present a polynomial-time algorithm for this problem when the optimization criterion is maximization of the minimum angle. Furthermore, we also provide a more general polynomial-time algorithm for finding the optimal placement of a constant number of Steiner points under the same optimization criterion.",

author = "Boris Aronov and Tetsuo Asano and Stefan Funke",

year = "2007",

doi = "10.1007/978-3-540-77120-3_59",

language = "English (US)",

isbn = "9783540771180",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "681--691",

booktitle = "Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings",

note = "18th International Symposium on Algorithms and Computation, ISAAC 2007 ; Conference date: 17-12-2007 Through 19-12-2007",

}