TITLE: Aspect-Ratio Voronoi Diagram with Applications

SPEAKER: Tetsuo Asano
          School of Information Science,
          JAIST (Japan Advanced Institute of Science and Technology)
          t-asano@jaist.ac.jp

ABSTRACT
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.