Triangulating polygons without large angles

Marshall Bern, David Dobkin, David Eppstein

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

6 Scopus citations

Abstract

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
Pages222-231
Number of pages10
ISBN (Print)0897915178, 9780897915175
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
EventEighth Annual Symposium On Computational Geometry - Berlin, Ger
Duration: Jun 10 1992Jun 12 1992

Publication series

NameEighth Annual Symposium On Computational Geometry

Other

OtherEighth Annual Symposium On Computational Geometry
CityBerlin, Ger
Period6/10/926/12/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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

Cite this