Abstract: The authors explore novel aspects of visibility for stationary and moving points inside a simple polygon P. They provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This results in a query time proportional to the size of visibility polygon but without cubic space overhead of earlier methods.
By exploring the connection between visibility polygons and shortest-path trees, the authors obtained a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside a simple polygon. The combination of the static and kinetic algorithms leads to a new static algorithm in which the authors trade off space for increased overhead in the query time.