An Optimal Algorithm for Computing Visibility in the Plane

DOI10.1137/S0097539791221505zbMath0828.68120OpenAlexW2041495686MaRDI QIDQ4326861

Paul J. Heffernan, Joseph S. B. Mitchell

Publication date: 8 January 1996

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

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

zbMATH Keywords

visibility polygonhidden line elimination

Mathematics Subject Classification ID

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

Related Items

Visibility queries in a polygonal region, Smoothing the Gap Between NP and ER, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Topological art in simple galleries, Reachable region query and its applications, Incremental Algorithms to Update Visibility Polygons, Trajectory planning for an articulated probe, Dynamic Algorithms for Visibility Polygons in Simple Polygons, Query point visibility computation in polygons with holes, Planar lower envelope of monotone polygonal chains, Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment, Computing the visibility polygon of an island in a polygonal domain, Visibility and ray shooting queries in polygonal domains, A linear time algorithm to remove winding of a simple polygon, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane