Approximating uniform triangular meshes in polygons

We consider the problem of triangulating a convex polygon using n Steiner points under the following optimality criteria: (1) minimizing the overall edge length ratio; (2) minimizing the maximum edge length; and (3) minimizing the maximum triangle perimeter. We establish a relation of these problems to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing constant approximations for all the optimality criteria above (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in these respects. The method is easy to implement and runs in O(n(2) logn) time and O(n) space. The observed runtime is much less. Moreover, for criterion (1) the method works-within the same complexity and approximation bounds-for arbitrary polygons with possible holes, and for criteria (2) and (3) it does so for a large subclass. (C) 2002 Elsevier Science B.V. All rights reserved.