The visibility complex

M Pocchiola*, G Vegter

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    83 Citations (Scopus)

    Abstract

    We introduce the visibility complex (rr 2-dimensional regular cell complex) of a collection of n pairwise disjoint convex obstacles in the plane. It can be considered as a subdivision of the set of free rays (i.e., rays whose origins lie in free space, the complement of the obstacles). Its cells correspond to collections of rays with the same backward and forward views. The combinatorial complexity of the visibility complex is proportional to the number k of free bitangents of the collection of obstacles. We give sn O(nlogn + k) time and O(k) working space algorithm for its construction. Furthermore we show how the visibility complex can be used to compute the visibility polygon from a point in O(mlogn) time, where m is the size of the visibility polygon. Our method is based on the notions of pseudotriangle and pseudo-triangulation, introduced in this paper.

    Original languageEnglish
    Pages (from-to)279-308
    Number of pages30
    JournalInternational journal of computational geometry & applications
    Volume6
    Issue number3
    DOIs
    Publication statusPublished - Sep-1996
    Event9th Annual ACM Symposium on Computational Geometry, as part of the 1993 Federated Computing Research Conference - , Canada
    Duration: 19-May-199321-May-1993

    Keywords

    • pseudotriangle
    • pseudo-triangulation
    • visibility polygon
    • visibility graph
    • visibility complex
    • computational geometry
    • COMPUTING VISIBILITY
    • ALGORITHM
    • GRAPH
    • PLANE
    • TIME

    Cite this