Visibility of disjoint polygons (Q1087340): Difference between revisions

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.