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
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
