New Results on Planar Triangulations.

Abstract

Several new results in planar triangulations are presented. In particular, an O(N sq log N) time worst-case algorithm for the construction of the 'greedy' triangulation is presented, an improvement over the previously best-known construction in time O(N cu). The minimum weight triangulation (MWT) of a simple N-vertex polygon is shown to be constructible in time O(N cu). A local property of MWTs is proved, a side result of which is that the shortest edge between a pair of points must be in a MWT. Also, it is shown that the Delaunay Triangulation is not 'approximately optimal', and that the ratio of the total length of the Delaunay Triangulation of N points to that of the MWT can be large as roughly N/2. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA085016

Entities

People

  • Peter D. Gilbert

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Dynamic Programming
  • Geometry
  • Illinois
  • Inclusions
  • Polygons
  • Security
  • Separators
  • Trees (Data Structures)
  • Triangles
  • Triangulation
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.