Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ International Journa...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://dx.doi.org/10.48550/ar...
Article . 2017
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Dynamic Algorithms for Visibility Polygons in Simple Polygons

Authors: R. Inkulu; K. Sowmya; Nitish P. Thakur;

Dynamic Algorithms for Visibility Polygons in Simple Polygons

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 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 [Formula: see text] due to the insertion (resp. deletion) of vertex [Formula: see text] to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of [Formula: see text] due to the insertion (resp. deletion) of [Formula: see text]. An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point [Formula: see text] in [Formula: see text] amid vertex insertions and deletions to the simple polygon. If [Formula: see text] is not exterior to the current simple polygon, then the visibility polygon of [Formula: see text] is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of [Formula: see text]. 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 [Formula: see text] due to the insertion of vertex [Formula: see text] 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 [Formula: see text] and [Formula: see text] due to the insertion of [Formula: see text]. 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. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple polygon during the preprocessing phase.

Keywords

Computational Geometry (cs.CG), FOS: Computer and information sciences, Computer Science - Computational Geometry

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    3
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3
Average
Average
Average
Green
bronze