An Optimal Algorithm for Computing Visibility in the Plane

DOI10.1137/S0097539791221505MaRDI QIDQ4326861zbMATH OpenOpenAlexFDO

Authors 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

hidden line eliminationvisibility polygon

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 177568
• scientific article; zbMATH DE number 2077120
• THE VISIBILITY COMPLEX
• Computing the visibility polygon of an island in a polygonal domain
• Topologically sweeping visibility complexes via pseudotriangulations

Cited in

(36)

• An algorithm for determining an opaque minimal forest of a convex polygon
• An \(O(n^ 3)\) algorithm for finding the minimal opaque forest of a convex polygon
• A fast algorithm for computing sparse visibility graphs
• Topologically sweeping visibility complexes via pseudotriangulations
• 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
• Computing the maximum clique in the visibility graph of a simple polygon
• A linear time algorithm to remove winding of a simple polygon
• An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
• Computing the visibility polygon of an island in a polygonal domain
• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• Incremental algorithms to update visibility polygons
• scientific article; zbMATH DE number 177568 (Why is no real title available?)
• scientific article; zbMATH DE number 1292991 (Why is no real title available?)
• scientific article; zbMATH DE number 559051 (Why is no real title available?)
• An optimal parallel algorithm for the visibility of a simple polygon from a point
• scientific article; zbMATH DE number 1102588 (Why is no real title available?)
• scientific article; zbMATH DE number 2077120 (Why is no real title available?)
• scientific article; zbMATH DE number 1445286 (Why is no real title available?)
• Planar lower envelope of monotone polygonal chains
• Smoothing the Gap Between NP and ER
• Computing the visibility polygon of an island in a polygonal domain
• Dynamic algorithms for visibility polygons in simple polygons
• scientific article; zbMATH DE number 5584308 (Why is no real title available?)
• Space–Query-Time Tradeoff for Computing the Visibility Polygon
• A sum of squares theorem for visibility (extended abstract)
• THE VISIBILITY COMPLEX
• Computing the visibility polygon from a convex set and related problems
• Optimal algorithm for shape from shading and path planning
• An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility.
• Topological art in simple galleries
• Visibility queries in a polygonal region

This page was built for publication: An Optimal Algorithm for Computing Visibility in the Plane

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