Triangulating polygons without large angles

Marshall Bern, David Dobkin, David Eppstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We show how to triangulate an n-vertex polygonal region - 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 is approximately as large as possible. Using O(n log n) triangles, we can also guarantee that the largest angle is no greater than 150°. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n1.85) triangles.

Original languageEnglish (US)
Title of host publicationEighth Annual Symposium On Computational Geometry
PublisherPubl by ACM
Number of pages10
ISBN (Print)0897915178, 9780897915175
StatePublished - 1992
EventEighth Annual Symposium On Computational Geometry - Berlin, Ger
Duration: Jun 10 1992Jun 12 1992

Publication series

NameEighth Annual Symposium On Computational Geometry


OtherEighth Annual Symposium On Computational Geometry
CityBerlin, Ger

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Triangulating polygons without large angles'. Together they form a unique fingerprint.

Cite this