New Algorithm to Speed up the Computation of a Visibility Graph

This poster describes a new algorithm called B# which is needed to find the visibility graph of a polygonal region with obstacles defined by simple polygons. It focuses on finding the entire visibility graph among polygonal obstacles which has been tuned in a variety of test cases. The obstacles are restricted to simple cases, i.e. where no edge intersects any other edges. The visibility graph problem itself has long been studied and has been applied to a variety of areas. A common use for it has been for finding the shortest path. The B# algorithm has been implemented adjustments made and experimental comparisons via time measurements carried out. A comparison between “Naïve algorithm” and “Naive algorithm with B#” was performed with different numbers of vertices. The B# algorithm by itself doesn’t calculate the visibility graph. It selects the next best obstacle where the calculation should proceed.