Feb 04: Polygon triangulation

views 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.

	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