• DocumentCode
    2892320
  • Title

    A quadratic time algorithm for the minmax length triangulation

  • Author

    Edelsbruneer, H. ; Tan, Tiow Seng

  • Author_Institution
    Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
  • fYear
    1991
  • fDate
    1-4 Oct 1991
  • Firstpage
    414
  • Lastpage
    423
  • Abstract
    It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time O(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics
  • Keywords
    computational geometry; minimax techniques; arbitrary normed metrics; maximum edge length; minmax length triangulation; quadratic time algorithm; relative neighborhood graph; triangulation; Approximation algorithms; Computer science; Minimax techniques; Polynomials; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Conference_Location
    San Juan
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185400
  • Filename
    185400
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2892320