An O(|E|log2 n) algorithm is presented to construct the visibility graph for a collection of n nonintersecting line segments, where |E| is the number of edges in the visibility graph. This algorithm is much faster than the O(n2)-time and O(n2)-space algorithms by Asano et al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses only O(n) working storage. © 1990 Springer-Verlag New York Inc.

Chandrasekharan Pandu Rangan

COMPUTERS, DIGITAL--COMPUTATIONAL METHODS

Computational geometry

Shortest path

Visibility graph

Mathematical techniques

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

A Fast Algorithm for Computing Sparse Visibility Graphs

Algorithmica

A fast algorithm for computing sparse visibility graphs

An O(|E|log2n) algorithm is presented to construct the visibility graph for a collection of n nonintersecting line segments, where |E| is the number of edges in the visibility graph. This algorithm is much faster than the O(n2)-time and O(n2)-space algorithms by Asano et al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses only O(n) working storage. © 1990 Springer-Verlag New York Inc.

Journal	Data powered by TypesetAlgorithmica
Publisher	Data powered by TypesetSpringer-Verlag
ISSN	01784617
Open Access	No