An Output-Sensitive Algorithm for Computing Visibility Graphs
From MaRDI portal
Publication:3982713
DOI10.1137/0220055zbMath0768.68202OpenAlexW1482503584MaRDI QIDQ3982713
David M. Mount, Subir Kumar Ghosh
Publication date: 26 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220055
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (58)
Computing minimum length paths of a given homotopy class ⋮ Area requirement of visibility representations of trees ⋮ Planar rectilinear shortest path computation using corridors ⋮ Can visibility graphs be represented compactly? ⋮ Characterizing and recognizing the visibility graph of a funnel-shaped polygon ⋮ Computing Simple Paths on Points in Simple Polygons ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ Finding exact solutions for the geometric firefighter problem in practice ⋮ The visibility-Voronoi complex and its applications ⋮ Fastest-path planning for direction-dependent speed functions ⋮ Minimal tangent visibility graphs ⋮ Shortest paths in the plane with obstacle violations ⋮ The vertex-edge visibility graph of a polygon ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Randomized approximation algorithms for planar visibility counting problem ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ Three dimensional weak visibility: Complexity and applications ⋮ A novel approach for modeling order picking paths ⋮ Link distance and shortest path problems in the plane ⋮ Incremental Algorithms to Update Visibility Polygons ⋮ Geometric path problems with violations ⋮ Algorithms for computing best coverage path in the presence of obstacles in a sensor field ⋮ Spiderman graph: visibility in urban regions ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ Approximate Shortest Paths in Polygons with Violations ⋮ Visibility Testing and Counting ⋮ A note on the combinatorial structure of the visibility graph in simple polygons ⋮ Computing the maximum clique in the visibility graph of a simple polygon ⋮ Perfect binary space partitions ⋮ Computing the visibility polygon of an island in a polygonal domain ⋮ Computing the full visibility graph of a set of line segments ⋮ Minimum-link paths among obstacles in the plane ⋮ Geometric Knapsack problems ⋮ Disproving a conjecture on planar visibility graphs ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ Continuous visible query for three-dimensional objects in spatial databases ⋮ An exact geometry-based algorithm for path planning ⋮ Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures ⋮ Minimum-link watchman tours ⋮ Unnamed Item ⋮ Density-Based Clustering Based on Topological Properties of the Data Set ⋮ An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem ⋮ An efficient algorithm for facility location in the presence of forbidden regions ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ Weighted minimum backward Fréchet distance ⋮ Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences ⋮ Three-dimensional weak visibility: Complexity and applications ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ Visibility testing and counting ⋮ On the union of fat wedges and separating a collection of segments by a line ⋮ Weak visibility queries of line segments in simple polygons ⋮ Weak visibility counting in simple polygons ⋮ A Computational Geometric Approach to Visual Hulls
This page was built for publication: An Output-Sensitive Algorithm for Computing Visibility Graphs
