Approximating uniform triangular meshes in polygons
F. Aurenhammer, N. Katoh, H. Kojima, M. Ohsaki, and Y.-F. Xu
We consider the problem of triangulating a convex polygon using
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
is chosen sufficiently large). That is, the produced
triangular mesh is uniform
in these respects. The method is easy to
implement and runs in
space. The observed
runtime is much less. Moreover, for criterion (1) the method works - within
the same complexity and approximation bounds - for arbitrary
with possible holes, and for criteria (2) and (3) it does so for a large
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].