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 -