Quadrilateral meshes with provable angle bounds

In this paper, we present an algorithm that utilizes a quadtree data structure to construct a quadrilateral mesh for a simple polygonal region in which no newly created angle is smaller than $${{18.43}}^{\circ} ({=}\hbox{arctan}(\frac{1}{3}))$$ or greater than $${{171.86}}^{\circ} ({=}{{135}}^{\circ} + 2\hbox{arctan}(\frac{1}{3}))$$. This is the first known result, to the best of our knowledge, on a direct quadrilateral mesh generation algorithm with a provable guarantee on the angles.