Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles

DOI10.1137/S0097539795253591zbMath0966.68081MaRDI QIDQ4507375

Sanjiv Kapoor, S. N. Maheshwari

Publication date: 18 October 2000

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

zbMATH Keywords

triangulationvisibility graphlinked listsobstaclesoutput-sensitivesimple polygon

Mathematics Subject Classification ID

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

Related Items (6)

Visibility queries in a polygonal region ⋮ Planar rectilinear shortest path computation using corridors ⋮ Routing among convex polygonal obstacles in the plane ⋮ Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

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