Given an orthogonal polygon with orthogonal holes, we devise a dynamic algorithm for guarding with vertex guards\cal \cal  , i.e., whenever orthogonal polygon is modified,\cal \cal  algorithm updates the set of vertex guards and their positions for guarding the modified orthogonal polygon\cal \cal  . Our algorithm modifies the guard placement locally while ensuring the updated orthogonal polygon with h holes and n vertices , is guarded using at most \lfloor (n+2h)/4 \rfloor vertex guards. The algorithm to update vertex guards after any modification to the polygon takes O(k \lg{(n+ n') time. Here, n' and n are the number of vertices of the orthogonal polygon before and after the update, respectively; and, k is the sum of the number of vertices added to or removed from the orthogonal polygon, the number of cuts in the L-shaped partitioning of the free space of the orthogonal polygon that got affected due to the update, and the number of channels affected due to the update. For the special case of the initial orthogonal polygon being hole-free, and each update resulting in a hole-free orthogonal polygon, our dynamic guard updating algorithmtakes O(k\lg{(n+n')) worst-case time. Initially, we preprocess the input orthogonal polygon with q vertices in O(q \lg{q}) time to construct data structures of size O(q\frac{\lg{q}}{\lg\lg{q}})}  .
We devise an algorithm for surveying a dynamic orthogonal polygonal domain\cal P by placing one guard at each vertex in a subset of vertices of\cal P , i.e., whenever an orthogonal polygon domain\cal P' is modified to result in another orthogonal polygonal domain\cal P, our algorithm updates the set of (vertex) guards surveying\cal P' so that the updated guard set surveys\cal P . Our algorithm modifies the guard placement in O(k \lg{(n+n') while ensuring the updated orthogonal polygon with h holes and n vertices is guarded using at most \lfloor (n+2h)/4 \rfloor vertex guards. For the special case of the initial orthogonal polygon being hole-free and each update resulting in a hole-free orthogonal polygon, our guard updation algorithm takes O(k \lg{(n+n') time. Here, n' and n are the number of vertices of the orthogonal polygon before and after the update, respectively; and, k is the sum of |n - n'| and the number of ) worst-case time. Initially, we preprocess the input orthogonal polygon with q vertices in O(q \lg{q}) time to construct data structures of size O(q\frac{\lg{q}}{\lg\lg{q}})} updates in a few structures maintained by our algorithm .
R
Given an orthogonal polygon with orthogonal holes, we devise a dynamic algorithm for guarding with vertex guards
We devise an algorithm for surveying a dynamic orthogonal polygonal domain
A
P by placing one guard at each vertex in a subset of vertices of
A
P
R
orthogonal polygon is modified,
an orthogonal polygon domain
A
P' is modified to result in another orthogonal polygonal domain
A
P, our
R
vertex guards and their positions for guarding the modified orthogonal polygon
(vertex) guards surveying
A
P' so that the updated guard set surveys
A
P
R
locally
in O(k \lg{(n+n')
D
,
R
The algorithm to update vertex guards after any modification to the polygon
For the special case of the initial orthogonal polygon being hole-free and each update resulting in a hole-free orthogonal polygon, our guard updation algorithm
R
\lg{(n+ n')
\lg{(n+n')
R
the number of vertices added to or removed from the orthogonal polygon, the number of cuts in the L-shaped partitioning of the free space of the orthogonal polygon that got affected due to the update,
|n - n'|
D
channels affected due to the update. For the special case of the initial orthogonal polygon being hole-free, and each update resulting in a hole-free orthogonal polygon, our dynamic guard updating algorithmtakes O(k\lg{(n+n')
A
updates in a few structures maintained by our algorithm