Feb 23: Faster polygon triangulation

From Jeff Erickson 2/23/2022

39 plays 0 comments

Intuition: Tracing the polygon can be faster than using the history dag
Crossing Lemma: E[#crossings] ≤ 4(n–r)
Seidel's algorithm: Alternate between randomized incremental (using history to locate points) and traversing the polygon (building conflict lists to locate points faster)
Balancing history time and tracing time: O(n log*n)

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