Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles

DOI10.1137/S0097539795253591MaRDI QIDQ4507375zbMATH OpenFDO

Authors Sanjiv Kapoor, S. N. Maheshwari

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539795253591

zbMATH Keywords

linked listsobstaclesoutput-sensitivesimple polygontriangulationvisibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• An optimal visibility graph algorithm for triangulated simple polygons
• THE VISIBILITY COMPLEX
• scientific article; zbMATH DE number 177568
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time

Cited in

(17)

• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• An optimal visibility graph algorithm for triangulated simple polygons
• Computing the full visibility graph of a set of line segments
• Topologically sweeping visibility complexes via pseudotriangulations
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
• Routing among convex polygonal obstacles in the plane
• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Spiderman graph: visibility in urban regions
• Crossing-Free Spanning Trees in Visibility Graphs of Points between Monotone Polygonal Obstacles
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
• Routing among convex polygonal obstacles in the plane
• A new algorithm for Euclidean shortest paths in the plane
• Routing among convex polygonal obstacles in the plane using a simplified domain
• Visibility queries in a polygonal region
• Planar rectilinear shortest path computation using corridors

This page was built for publication: Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507375)