Dynamic algorithms for visibility polygons in simple polygons

DOI10.1142/S021819592050003XMaRDI QIDQ5149571zbMATH OpenOpenAlexFDO

Authors Rajasekhar Inkulu, K. Sowmya, Nitish P. Thakur

Publication date 11 February 2021

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.08219

zbMATH Keywords

computational geometryvisibilitydynamic algorithms

Mathematics Subject Classification ID

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

Abstract: We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and/or deletions to the simple polygon. * A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point $q$ due to the insertion (resp. deletion) of vertex $v$ to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of $q$ due to the insertion (resp. deletion) of $v$. * An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point $p$ in $mathbb{R}^2$ amid vertex insertions and deletions to the simple polygon. If $p$ is not exterior to the current simple polygon, then the visibility polygon of $p$ is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of $p$. * An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment $pq$ due to the insertion of vertex $v$ to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at $p$ and $q$ due to the insertion of $v$. * An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon.

Recommendations

• Maintaining the visibility graph of a dynamic simple polygon
• Incremental algorithms to update visibility polygons
• Visibility queries and maintenance in simple polygons
• scientific article; zbMATH DE number 177567
• Efficient visibility queries in simple polygons

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• A linear algorithm for computing the visibility polygon from a point
• An Optimal Algorithm for Computing Visibility in the Plane
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Computing the visibility polygon from a convex set and related problems
• Computing the visibility polygon from an edge
• Corrections to Lee's visibility polygon algorithm
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Efficient computation of query point visibility in polygons with holes
• Efficient visibility queries in simple polygons
• Incremental algorithms to update visibility polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Maintenance of configurations in the plane
• Optimal shortest path queries in a simple polygon
• The Robot Localization Problem
• The visibility diagram: A data structure for visibility problems and motion planning
• Visibility Algorithms in the Plane
• Visibility and intersection problems in plane geometry
• Visibility and ray shooting queries in polygonal domains
• Visibility of a simple polygon
• Visibility of disjoint polygons
• Visibility queries and maintenance in simple polygons
• Visibility queries in a polygonal region
• Weak visibility queries of line segments in simple polygons and polygonal domains

Cited in

(13)

• scientific article; zbMATH DE number 1102588 (Why is no real title available?)
• An algorithm for dynamic Delaunay triangulation of simple polygon
• Vertex guarding for dynamic orthogonal art galleries
• Maintaining the visibility graph of a dynamic simple polygon
• Optimal Area Polygonization by Triangulation and Visibility Search
• scientific article; zbMATH DE number 177567 (Why is no real title available?)
• New Results on Visibility in Simple Polygons
• A space-time trade-off for computing the visibility polygon in the multi-pass model
• An Algorithm for Determining Visibility of a Simple Polygon from an Internal Line Segment
• An optimal visibility graph algorithm for triangulated simple polygons
• Incremental algorithms to update visibility polygons
• Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
• Visibility queries and maintenance in simple polygons

This page was built for publication: Dynamic algorithms for visibility polygons in simple polygons

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