Dynamic Algorithms for Visibility Polygons in Simple Polygons

摘要

We devise the following dynamic algorithms for both maintaining as well asquerying for the visibility and weak visibility polygons amid vertex insertionsand/or deletions to the simple polygon. * A fully-dynamic algorithm for maintaining the visibility polygon of a fixedpoint located interior to the simple polygon amid vertex insertions anddeletions to the simple polygon. The time complexity to update the visibilitypolygon 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 ofcombinatorial changes needed to the visibility polygon of $q$ due to theinsertion (resp. deletion) of $v$. * An output-sensitive query algorithm to answer the visibility polygon querycorresponding to any point $p$ in $mathbb{R}^2$ amid vertex insertions anddeletions to the simple polygon. If $p$ is not exterior to the current simplepolygon then the visibility polygon of $p$ is computed. Otherwise, ouralgorithm outputs the visibility polygon corresponding to the exteriorvisibility of $p$. * An output-sensitive algorithm to compute the weak visibility polygoncorresponding to any query line segment located interior to the simple polygonamid both the vertex insertions and deletions to the simple polygon. Each of these algorithms require preprocessing the initial simple polygon.And, the algorithms that maintain the visibility polygon (resp. weak visibilitypolygon) compute the visibility polygon (resp. weak visibility polygon) withrespect to the initial simple polygon during the preprocessing phase.