Minimal tangent visibility graphs

DOI10.1016/0925-7721(95)00016-XzbMATH Open0857.68103MaRDI QIDQ1924714FDOQ1924714

Authors: Michel Pocchiola, Gert Vegter 

Publication date: 20 October 1996

Published in: Computational Geometry (Search for Journal in Brave)

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

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)

Cites Work

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

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
• Measuring the quality of surveillance in a wireless sensor network
• Convexity minimizes pseudo-triangulations
• Segment endpoint visibility graphs are Hamiltonian

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)