Size Competitive Meshing without Large Angles

ICALP: 34th International Colloquium on Automata, Languages and Programming
2007

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^\circ$.
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.

@inproceedings{miller07size, Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy}, Booktitle = {34th International Colloquium on Automata, Languages and Programming}, Title = {Size Competitive Meshing without Large Angles}, Year = {2007}}