New Results on Planar Triangulations.
Peter D Gilbert · Defense Technical Information Center (DTIC) · 1979
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)