TY - JOUR
T1 - Optimal triangulations of points and segments with Steiner points
AU - Aronov, Boris
AU - Asano, Tetsuo
AU - Funke, Stefan
N1 - Funding Information:
In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time ∗Work by B.A. has been partially supported by a grant from the U.S.-Israel Binational Science Foundation and by NSA MSP Grant H98230-06-1-0016. †Work by T.A. was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research on Priority Areas and Scientific Research (B). Part of the work of T.A. was performed while he was visiting Max-Planck-Institut für Informatik, Germany, Carleton University, Canada, and New York University, USA, all in 2006. ‡Work by S.F. was partially supported by the Max Planck Center for Visual Computing and Communication (MPC-VCC) funded by the German Federal Ministry of Education and Research (FKZ 01IMC01).
PY - 2010/2
Y1 - 2010/2
N2 - Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.
AB - Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.
KW - Computational geometry
KW - Constrained Delaunay triangulation
KW - Geometric optimization
KW - Polynomial-time algorithm
KW - Steiner point
KW - Triangulation
KW - Voronoi diagram
UR - http://www.scopus.com/inward/record.url?scp=77951689945&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951689945&partnerID=8YFLogxK
U2 - 10.1142/S0218195910003219
DO - 10.1142/S0218195910003219
M3 - Article
AN - SCOPUS:77951689945
SN - 0218-1959
VL - 20
SP - 89
EP - 104
JO - International Journal of Computational Geometry and Applications
JF - International Journal of Computational Geometry and Applications
IS - 1
ER -