The visibility complex
Michel Pocchiola, Gert Vegter · 1993
We introduce the visibility complex of a collection O of n pairwise disjoint convex objects in the plane. This 2 dimensional cell complex may be considered as a generalization of the tangent visibility graph of 0. Its space complexity k is proportional to the size of the tangent visibility graph. We give an O(nlog n+k) algorithm for its construction. Furthermore we show how the visibility complex can be used to compute the view from a point or a convex object with respect to O in O(m log n) time, where m is the size of the view. The view from a point is a generalization of the visibility polygon of that point with respect to O.