LMT-skeleton heuristics for several new classes of optimal triangulations

Given a planar point set, we consider three classes of optimal triangulatio ns: (1) the minimum weight triangulation with angular constraints (constrai nts on the minimum angle and the maximum angle in a triangulation), (2) the angular balanced triangulation which minimizes the sum of the ratios of th e maximum angle to the minimum angle for each triangle, and (3) the area ba lanced triangulation which minimizes the variance of the areas of triangles in the triangulation. With appropriate definition of local optimality for each class, a simple unified method is established for the computation of t he subgraphs of optimal triangulations. Computational experiments demonstra te that the method successfully identifies large portion of edges of the op timal triangulations of each class for all problem instances tested, and he nce optimal triangulations for each class can be obtained from them by appl ying dynamic programming. (C) 2000 Elsevier Science B.V. All rights reserve d.