Optimal triangulation with steiner points

Boris Aronov, Tetsuo Asano, Stefan Funke

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
    PublisherSpringer Verlag
    Number of pages11
    ISBN (Print)9783540771180
    StatePublished - 2007
    Event18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan
    Duration: Dec 17 2007Dec 19 2007

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4835 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other18th International Symposium on Algorithms and Computation, ISAAC 2007

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Optimal triangulation with steiner points'. Together they form a unique fingerprint.

    Cite this