VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME

DOI10.1142/S0218195900000309MaRDI QIDQ4762913zbMATH OpenOpenAlexFDO

Authors Mark J. Keil, David M. Mount, S. Wismath

Publication date 13 September 2001

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195900000309

zbMATH Keywords

visibility graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A fast algorithm for computing sparse visibility graphs
• Computing the full visibility graph of a set of line segments
• scientific article; zbMATH DE number 177568
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Topologically sweeping visibility complexes via pseudotriangulations

Cites work

• A tight lower bound on the size of visibility graphs
• An optimal visibility graph algorithm for triangulated simple polygons
• Computing the full visibility graph of a set of line segments
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Minimal visibility graphs
• On the identification of the convex hull of a finite set of points in the plane
• Shortest path solves edge-to-edge visibility in a polygon
• THE VISIBILITY COMPLEX
• Triangulating a simple polygon in linear time
• Visibility of disjoint polygons

Cited in

(2)

• Alternating paths along axis-parallel segments
• Segment endpoint visibility graphs are Hamiltonian

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4762913)