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

DOI10.1142/S0218195900000309zbMATH Open0968.68122OpenAlexW2116409181MaRDI QIDQ4762913FDOQ4762913

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

Recommendations

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

zbMATH Keywords

visibility graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

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

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)