Linear-size nonobtuse triangulation of polygons
| Author(s) : | Scott Mitchell Marshall Bern Scott Mitchell Marshall Bern, |
| Publisher : | N/A |
| Publication Date : | 1994 |
| ISSN : | N/A |
| Abstract : | Abstract We give an algorithm for triangulating n-vertex polyg-onal regions (with holes) so that no angle in the final triangulation measures more than r/2. The number of triangles in the triangu-lation is only O(n), improving a previous bound of O(n2), and the worst-case running time is O(nlog 2 n). The basic technique used in the algorithm, recursive subdivision by disks, is new and may have wider application in mesh generation. We also report on an implementation of our algorithm., |