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 $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 \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.

Reference: F. Aurenhammer, N. Katoh, H. Kojima, M. Ohsaki, and Y.-F. Xu. Approximating uniform triangular meshes in polygons. In Proc. $6^{th}$ Ann. Intl. Computing and Combinatorics Conference, Lecture Notes in Computer Science, volume 1558, pages 23-33, Sydney, Australia, 2000. Springer Verlag.