No label defined (Q3798256)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4064506
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4064506

      Statements

      1988
      0 references
      Voronoi diagram
      0 references
      computational geometry
      0 references
      greedy triangulation
      0 references
      planar straight-line graph
      0 references
      time-performance
      0 references
      0 references
      [For the entire collection see Zbl 0643.00031.] An algorithm for constructing the greedy triangulation of any planar straight-line graph with n vertices in time \(O(n^ 2 \log n)\) and space O(n) is presented. The upper time-space bound implied by the algorithm in particular improves Gilbert's simultaneous \(O(n^ 2 \log n)\)-time and \(O(n^ 2)\)-space bound for finding the greedy triangulation of an n- point planar point set. A theorem suggesting a good expected time- performance of the presented algorithm is proved.
      0 references

      Identifiers