TRIANGULATING POLYGONS WITHOUT LARGE ANGLES
- 1 March 1995
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 5 (1) , 171-192
- https://doi.org/10.1142/s0218195995000106
Abstract
We show how to triangulate polygonal regions—adding extra vertices as necessary— with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. Using O(n log n) triangles for simple polygons or O(n3/2) triangles for polygons with holes, we can guarantee that the largest angle is no greater than 150°. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n1.85) triangles.Keywords
This publication has 0 references indexed in Scilit: