Apr 22: Visibility graphs

views comments

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.

	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