The Visibility Graph Among Polygonal Obstacles: a Comparison of Algorithms
John Kitzinger · 2003
This paper examines differences of four approaches in finding the visibility graph of a polygonal region with obstacles defined by simple polygons. Each has been implemented and tuned. Experimental comparisons via time measurements have been carried out against a variety of testcases ranging in graph density from maximal, O ( n 2), to minimal, W(n). In this manner, expected asymptotic time bounds have been verified with crossover points between the algorithms identified.