Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time (Q1062764): Difference between revisions

Given a set S of line segments in the plane, its visibility graph \(G_ S\) is the undirected graph which has the endpoints of the line segments in S as nodes and in which two nodes (points) are adjacent whenever they 'see' each other (the line segments in S are regarded as nontransparent obstacles). It is shown that \(G_ S\) can be constructed in \(O(n^ 2)\) time and space for a set S of n nonintersecting line segments. As an immediate implication, the shortest path between two points in the plane avoiding a set of a nonintersecting line segments can be computed in \(O(n^ 2)\) time and space.