Feb 18: Randomized Incremental Construction II
From Jeff Erickson
…Read more Less…
- Review of insertion algorithm: expected time = O(1) plus point location
- Conflict lists: Every trapezoid knows which points it contains
- Backward analysis: O(n log n) expected time
- Special case: Randomized quicksort!
- History dag: Record changes to the decomposition as a data structure
- Backward analysis: O(log n) expected time to locate any point
- Special case: Treaps!