Tetsuo Asano
School of Information Science,
JAIST (Japan Advanced Institute of Science and Technology)
Triangulation is quite important in many areas such as Finete Element Method and computer graphics. In a simple setting we would like to triangulate a simple polygon possibly using a number of internal points. Since a flat or skinny triangle may cause numerical errors, we would like to improve a triangulation if such triangles are included. More precisely, triangles are evaluated by their aspect ratios, which are defined by the ratio between the longest and shortest sides or between the longest side and its corresponding height. Our ultimate goal is to optimize the worst aspect ratio of triangles contained by moving internal points (since polygon vertices are fixed). The problem of achieving the best triangulation in the sense looks quite hard. So, our secondary goal is local improvement of a triangulation. That is, given a triangulation, we find an internal point incident to a triangle of the worst aspect ratio and move it to a locally optimal point in its neighborhood. More precisely, once we find such an internal point p, remove all triangles incident to p. Then, we have a star-shaped polygon (or a convex polygon) around the point. We want to find a point q such that the worst aspect ratio among the triangles resulting by drawing chords from q to all the vertices of the star-shaped polygon is optimized. We can show that such a point is a vertex of a Voronoi diagram, called an aspect-ratio Voronoi diagram which is defined as follows.
Given a set of line segments in the plane, a point belongs to a Voronoi region of a line segment if the aspect ratio of a triangle defined by the point and the line segment is largest among all line segments. These Voronoi diagrams are different from an ordinary Voronoi diagram for a point set. After introducing interesting properties, we present three efficient algorithms for finding a point to minimize the largest aspect ratio.