Minimal tangent visibility graphs

DOI10.1016/0925-7721(95)00016-XMaRDI QIDQ1924714zbMATH OpenFDO

Authors Michel Pocchiola, Gert Vegter

Publication date 20 October 1996

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(95)00016-X

zbMATH Keywords

visibility graphsDavenport-Schinzel sequencesrelative convex hulls

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the minimum size of visibility graphs
• A tight lower bound on the size of visibility graphs
• Minimal visibility graphs
• scientific article; zbMATH DE number 841640
• On the connectivity of visibility graphs

Cites work

• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• A fast algorithm for computing sparse visibility graphs
• A note on minimal visibility graphs
• A tight lower bound on the size of visibility graphs
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• COMPUTATIONAL GEOMETRY COLUMN 18
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Minimal visibility graphs
• Rotation and Winding Numbers for Planar Polygons and Curves
• Shortest paths in the plane with convex polygonal obstacles
• Theory of Maps on Orientable Surfaces
• Time and space efficient algorithms for shortest paths between convex polygons
• Topologically sweeping an arrangement
• Topologically sweeping visibility complexes via pseudotriangulations
• Visibility of disjoint polygons

Cited in

(12)

• On the minimum size of visibility graphs
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• Pointed binary encompassing trees: simple and optimal
• Topologically sweeping visibility complexes via pseudotriangulations
• Alternating paths along axis-parallel segments
• Minimum weight pseudo-triangulations
• Tight degree bounds for pseudo-triangulations of points
• On the number of pseudo-triangulations of certain point sets
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• Convexity minimizes pseudo-triangulations
• Segment endpoint visibility graphs are Hamiltonian
• Measuring the quality of surveillance in a wireless sensor network

This page was built for publication: Minimal tangent visibility graphs

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