Computing a visibility polygon using few variables

DOI10.1016/J.COMGEO.2014.04.001MaRDI QIDQ396475zbMATH OpenOpenAlexFDO

Authors Matias Korman, Stefan Langerman, Rodrigo I. Silveira, Luis Barba

Publication date 13 August 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2014.04.001

zbMATH Keywords

algorithmcomputational geometryfacility locationvisibilityroboticsdivide-and-conquersimple polygonconvex vertexreflex vertexvisibility polygon

Mathematics Subject Classification ID

Kinematics of mechanisms and robots (70B15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational issues in computer and robotic vision (65D19)

Recommendations

• Computing the visibility polygon using few variables
• Computing the visibility polygon from an edge
• Computing the visibility graph of points within a polygon
• scientific article; zbMATH DE number 1424307
• Visibility queries and maintenance in simple polygons

Cites work

• A generalized Winternitz theorem
• Comparison-based time-space lower bounds for selection
• Computational Complexity
• Computing the visibility polygon using few variables
• Constant-work-space algorithm for a shortest path in a simple polygon
• Constant-work-space algorithms for geometric problems
• Corrections to Lee's visibility polygon algorithm
• Geodesic ham-sandwich cuts
• Geodesic order types
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Multi-pass geometric algorithms
• On the identification of the convex hull of a finite set of points in the plane
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Space-time trade-offs for stack-based algorithms
• Upper bounds for time-space trade-offs in sorting and selection
• Visibility Algorithms in the Plane

Cited in

(11)

• Computing the visibility polygon using few variables
• Space-time trade-offs for stack-based algorithms
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Time-space trade-off for finding the \(k\)-visibility region of a point in a polygon
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Time-space trade-offs for triangulations and Voronoi diagrams
• Time-space trade-offs for triangulations and Voronoi diagrams
• A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
• scientific article; zbMATH DE number 4090791 (Why is no real title available?)
• Experimental study of compressed stack algorithms in limited memory environments
• Computing the visibility polygon from an edge

This page was built for publication: Computing a visibility polygon using few variables

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