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 geometryconvex vertexdivide-and-conquerfacility locationreflex vertexroboticssimple polygonvisibilityvisibility polygon

Mathematics Subject Classification ID

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

Review text

This paper brings a novel approach for computing the visibility polygon of a given viewpoint inside of a simple polygon with both reflex and convex vertices. The visibility polygon is defined as the set of all points of the simple polygon that can be seen from the viewpoint, where two points (the given viewpoint and the point inside the simple polygon) can see each other whenever the segment given by these two points is contained in the simple polygon. The significant influence of reflex vertices on the visibility polygon is considered and the running time of the developed algorithms is expressed not only in terms of the complexity of the simple polygon but also in terms of the number of reflex vertices. Both the developed algorithms (output sensitive and a divide-and-conquer) described in the paper can be useful in computational geometry, robotics, video games, determining positions to locate facilities, etc.

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)

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

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)