Finding a covering triangulation whose maximum angle is provably small.

摘要

Given a planar straight-line graph, we find a covering triangulation whose maximum angle is as small as possible. A covering triangulation is a triangulation whose vertex set contains the input vertex set and whose edge set contains the input edge set. Such a triangulation differs from the usual Steiner triangulation in that we may not add a Steiner vertex on any input edge. Covering triangulations provide a convenient method for triangulating multiple regions sharing a common boundary, as each region can be triangulated independently. As it is possible that no finite covering triangulation is optimal in terms of its maximum angle, we propose an approximation algorithm. Our algorithm produces a covering triangulation whose maximum angle (gamma) is probably close to (gamma)(sub opt), a lower bound on the maximum angle in any covering triangulation of the input graph. Note that we must have (gamma) (le) 3(gamma)(sub opt), since we always have (gamma)(sub opt) (ge) (pi)/3 and no triangulation can contain an angle of size greater than (pi). We prove something significantly stronger. We show that (pi) (minus) (gamma) (ge) ((pi) (minus) (gamma)(sub opt))/6, i.e., our (gamma) is not much closer to (pi) than is (gamma)(sub opt). This result represents the first nontrivial bound on a covering triangulation's maximum angle. We require a subroutine for the following problem: Given a polygon with holes, find a Steiner triangulation whose maximum angle is bounded away from (pi). No angle larger than 8(pi)/9 is sufficient for the bound on (gamma) claimed above. The number of Steiner vertices added by our algorithm and its running time are highly dependent on the corresponding bounds for the subroutine. Given an n-vertex planar straight-line graph, we require O(n + S(n)) Steiner vertices and O(n log n + T(n)) time, where S(n) is the number of Steiner vertices added by the subroutine and T(n) is its running time for an O(n)-vertex polygon with holes.