# Approximating uniform triangular meshes in polygons

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

### Abstract:

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.

Reference: F. Aurenhammer, N. Katoh, H. Kojima, M. Ohsaki, and Y.-F. Xu. Approximating uniform triangular meshes in polygons. Theoretical Computer Science, 289:879-895, 2002. Special Issue. [SFB Report F003-159, TU Graz, Austria, 1999].