Feb 04: Polygon triangulation

From Jeff Erickson 2/4/2022

110 plays 0 comments

Definitions: simple polygon, triangulation
Look, it's the Jordan Curve Theorem! [Bolzano 184x, Jordan 1887]
Jordan polygon theorem and the triangulation theorem [Schönflies 1896, Dehn 1899, Lennes 1911]
Lemma: Every simple polygon with more than three vertices has an interior diagonal [Dehn, Lennes]
Quicksort-like algorithm runs in O(n^2) time
Trapezoidal decompositions: definition, construction in O(n log n) time
Boring trapezoids contain diagonals
Monotone mountains: All trapezoids are interesting
Any mountain can be triangulated with three pennies in O(n) time.

Loading…

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois

Related Media