Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
From MaRDI portal
Publication:1062764
DOI10.1016/0020-0190(85)90044-4zbMath0573.68036OpenAlexW2014320134WikidataQ54309986 ScholiaQ54309986MaRDI QIDQ1062764
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90044-4
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (52)
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles ⋮ Visibility of disjoint polygons ⋮ Planar rectilinear shortest path computation using corridors ⋮ Can visibility graphs be represented compactly? ⋮ The visibility diagram: A data structure for visibility problems and motion planning ⋮ Time and space efficient algorithms for shortest paths between convex polygons ⋮ A tight lower bound on the size of visibility graphs ⋮ Solving visibility problems on MCCs of smaller size ⋮ Routing among convex polygonal obstacles in the plane ⋮ A new algorithm for shortest paths among obstacles in the plane ⋮ Parallel algorithms for shortest path problems in polygons ⋮ On a class of \(O(n^ 2)\) problems in computational geometry ⋮ Shortest paths among transient obstacles ⋮ Obstacle growing in a nonpolygonal world ⋮ Shortest path between two simple polygons ⋮ Rectilinear shortest paths in the presence of rectangular barriers ⋮ A tight lower bound for the complexity of path-planning for a disc ⋮ On fast planning of suboptimal paths amidst polygonal obstacles in plane ⋮ An optimal visibility graph algorithm for triangulated simple polygons ⋮ An algorithmic approach to some problems in terrain navigation ⋮ Routing in polygonal domains ⋮ Topologically sweeping an arrangement ⋮ A survey of motion planning and related geometric algorithms ⋮ Minimal tangent visibility graphs ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ On a class of \(O(n^2)\) problems in computational geometry ⋮ On maximum flows in polyhedral domains ⋮ Visibility graphs and obstacle-avoiding shortest paths ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On graphs preserving rectilinear shortest paths in the presence of obstacles ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ Perfect binary space partitions ⋮ Search for shortest path around semialgebraic obstacles in the plane ⋮ Applications of random sampling to on-line algorithms in computational geometry ⋮ Computing the visibility polygon of an island in a polygonal domain ⋮ Computing the full visibility graph of a set of line segments ⋮ An exact geometry-based algorithm for path planning ⋮ Topological sweep of the complete graph ⋮ Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures ⋮ Density-Based Clustering Based on Topological Properties of the Data Set ⋮ Planning a time-minimal motion among moving obstacles ⋮ Unnamed Item ⋮ A fast algorithm for computing sparse visibility graphs ⋮ Efficient randomized algorithms for some geometric optimization problems ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ There are planar graphs almost as good as the complete graph ⋮ Rectilinear paths among rectilinear obstacles ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane ⋮ VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME ⋮ Routing in Polygonal Domains ⋮ A workbench for computational geometry
Cites Work
This page was built for publication: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
