Visibility of disjoint polygons (Q1087340)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Visibility of disjoint polygons
scientific article

    Statements

    Visibility of disjoint polygons (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    1986
    0 references
    Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in \(O(n^ 2)\) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in \(O(n^ 2)\) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in \(O(n^ 2)\) time, improving earlier \(O(n^ 2 \log n)\) results.
    0 references
    0 references
    0 references
    0 references
    0 references
    computational geometry
    0 references
    computer graphics
    0 references
    robotics
    0 references
    hidden-line elimination
    0 references
    data structure
    0 references
    visibility polygon
    0 references
    visibility graph
    0 references
    shortest path
    0 references