Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
type: Item
instance of: scholarly article
title: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
zbMATH Open document ID: 0573.68036
DOI: 10.1016/0020-0190(85)90044-4
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3915643
zbMATH Keywords: computational geometry
zbMATH Keywords: shortest path
Wikidata QID: Q54309986
author: Emo Welzl
MaRDI profile type: Publication
full work available at URL: 0020-0190(85)90044-4
OpenAlex ID: W2014320134
cites work: A note on two problems in connexion with graphs
cites work: Constructing Arrangements of Lines and Hyperplanes with Applications
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Q3219752
DBLP publication ID: journals/ipl/Welzl85
description: scientific article; zbMATH DE number 3915643