Apr 22: Visibility graphs
From Jeff Erickson
…Read more Less…
- Visibility graph definitions
- Complexity: Θ(n) best case, Θ(n^2) worst case
- Construction via sweep of dual line arrangement: O(n^2 log n) time
- Four types of events
- Topological sweep: O(n^2) time
- Maintain trapezoidal decomposition: O(n log n = k log n) time.
- Sketch of Pocchiola and Vegter's greedy pseudotriangulation algorithm: O(n log n + k) time.