Title: Constructing the visibility graph for n-line segments in O(n2) time
Abstract: Given a set S of line segments in the plane, its visibility graph GS 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 GS can be constructed in O(n2) 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 n nonintersecting line segments can be computed in O(n2) time and space
Publication Year: 1985
Publication Date: 1985-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 284
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot