Optimal triangulations of points and segments with Steiner points

Boris Aronov, Tetsuo Asano, Stefan Funke

    Research output: Contribution to journalArticlepeer-review


    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 languageEnglish (US)
    Pages (from-to)89-104
    Number of pages16
    JournalInternational Journal of Computational Geometry and Applications
    Issue number1
    StatePublished - Feb 2010


    • 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


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

    Cite this