The Visibility Complex

Michel Pocchiola, Gert Vegter

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

25 Citations (Scopus)
109 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages10
Publication statusPublished - 1993

Cite this