finding the visibility graph of a simple polygon in time proportional to its size
Let P be a given simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P . We describe an algorithm that finds the visibility graph of P in &Ogr; ( m + n log log n ) time, where m is the number of edges in the visibility graph. Because m can be as small as &Ogr; ( n ), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take &THgr;( n 2 ) time.
visibility graph polygon timing size segmentation algorithm log general