**F. Aurenhammer, N. Katoh, H. Kojima, M. Ohsaki, and Y.-F. Xu**

We consider the problem of triangulating a convex polygon using 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 is chosen sufficiently large). That is, the produced
triangular mesh is *uniform* in these respects. The method is easy to
implement and runs in time and 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.