Minimal tangent visibility graphs

DOI10.1016/0925-7721(95)00016-XzbMath0857.68103MaRDI QIDQ1924714

Michel Pocchiola, Gert Vegter

Publication date: 20 October 1996

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

zbMATH Keywords

visibility graphs; Davenport-Schinzel sequences; relative convex hulls

Mathematics Subject Classification ID

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

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Convexity minimizes pseudo-triangulations, Pointed binary encompassing trees: simple and optimal, Alternating paths along axis-parallel segments, Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time, Segment endpoint visibility graphs are Hamiltonian, On the minimum size of visibility graphs, Topologically sweeping visibility complexes via pseudotriangulations, Tight degree bounds for pseudo-triangulations of points, Minimum weight pseudo-triangulations, Decompositions, partitions, and coverings with convex polygons and pseudo-triangles, On the number of pseudo-triangulations of certain point sets, MEASURING THE QUALITY OF SURVEILLANCE IN A WIRELESS SENSOR NETWORK

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Time and space efficient algorithms for shortest paths between convex polygons
• A tight lower bound on the size of visibility graphs
• Topologically sweeping an arrangement
• A fast algorithm for computing sparse visibility graphs
• A note on minimal visibility graphs
• Topologically sweeping visibility complexes via pseudotriangulations
• Minimal visibility graphs
• Rotation and Winding Numbers for Planar Polygons and Curves
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Theory of Maps on Orientable Surfaces
• COMPUTATIONAL GEOMETRY COLUMN 18