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 O. Its space complexity k is proportional to the size of the tangent visibility graph. We give an O(n log 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.
|Title of host publication||EPRINTS-BOOK-TITLE|
|Publisher||University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science|
|Number of pages||10|
|Publication status||Published - 1993|