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^° (=arctan(\frac13)){{18.43}}^{\circ} ({=}\hbox{arctan}(\frac{1}{3})) or greater than 171.86^° (=135^° + 2arctan(\frac13)){{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.