Size Competitive Meshing without Large Angles

We present a new meshing algorithm for the plane, Overlay Stitch
Meshing (OSM), accepting as input an arbitrary Planar Straight Line
Graph and producing a triangulation with all angles smaller than
170^o.  The output triangulation has competitive size with any
optimal size mesh having equally bounded largest angle.  The
competitive ratio is $O(\log(L/s))$ where $L$ and $s$ are respectively
the largest and smallest features in the input. OSM runs in $O(n \log
(L/s) + m)$ time/work where $n$ is the input size and $m$ is the
output size.  The algorithm first uses Sparse Voronoi Refinement to
compute a quality overlay mesh of the input points alone.  This
triangulation is then combined with the input edges to give the final
mesh.