### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 89-104 |

Number of pages | 16 |

Journal | International Journal of Computational Geometry and Applications |

Volume | 20 |

Issue number | 1 |

DOIs | |

State | Published - Feb 2010 |

### Keywords

- Computational geometry
- Constrained Delaunay triangulation
- Geometric optimization
- Polynomial-time algorithm
- Steiner point
- Triangulation
- Voronoi diagram

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Optimal triangulations of points and segments with Steiner points'. Together they form a unique fingerprint.

## Cite this

*International Journal of Computational Geometry and Applications*,

*20*(1), 89-104. https://doi.org/10.1142/S0218195910003219