Dynamic algorithms for visibility polygons in simple polygons

DOI10.1142/S021819592050003XzbMATH Open1457.68292arXiv1704.08219OpenAlexW3082218119MaRDI QIDQ5149571FDOQ5149571

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)

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.

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

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

zbMATH Keywords

computational geometryvisibilitydynamic algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• An algorithm for dynamic Delaunay triangulation of simple polygon
• Vertex guarding for dynamic orthogonal art galleries
• Optimal Area Polygonization by Triangulation and Visibility Search
• Maintaining the visibility graph of a dynamic simple polygon
• Title not available (Why is that?)
• New Results on Visibility in Simple Polygons
• An Algorithm for Determining Visibility of a Simple Polygon from an Internal Line Segment
• A space-time trade-off for computing the visibility polygon in the multi-pass model
• 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)