An Optimal Algorithm for Computing Visibility in the Plane

DOI10.1137/S0097539791221505zbMath0828.68120MaRDI 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 polygon; hidden line elimination

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

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