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²log n) 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.