We consider the problem of updating the visibility polygon of a point located within the given simple polygon as that polygon is modified with the incremental addition of new vertices to it. In particular, we propose the following two semi-dynamic algorithms: 1. Given a simple polygon P defined with n vertices and a point p ∈ P, our preprocessing algorithm computes the visibility polygon of p in P and constructs relevant data structures in O(n) time; for every vertex v added to the current simple polygon, our visibility polygon updation algorithm takes O((k + 1) lg n) time in the worst-case to update the visibility polygon of p in the new simple polygon resulted from adding v. Here, k is the change in combinatorial complexity of visibility polygon of p due to the addition of new vertex v. 2. Given a simple polygon P defined with n vertices and an edge pq of P, our preprocessing algorithm computes the weak visibility polygon of pq in P and constructs relevant data structures in O(n) time; for every vertex v added to the current simple polygon, our weak visibility updation algorithm takes O((k+1) lg n) time in the worst-case to update the weak visibility polygon of pq in the new simple polygon resulted from adding v. Here, k is the change in combinatorial complexity of shortest path tree rooted at p added to the change in combinatorial complexity of shortest path tree rooted at q, wherein both these changes are due to the addition of new vertex v.
展开▼
