Vertex Guarding for Dynamic Orthogonal Art Galleries.

We devise an algorithm for surveying a dynamic orthogonal polygonal domain by placing one guard at each vertex in a subset of its vertices, i.e., whenever an orthogonal polygonal domain ′ is modified to result in another orthogonal polygonal domain , our algorithm updates the set of vertex guards surveying ′ so that the updated guard set surveys . Our algorithm modifies the guard placement in O (k lg (n + n ′)) amortized time, while ensuring the updated orthogonal polygonal domain with h holes and n vertices is guarded using at most ⌊ (n + 2 h) / 4 ⌋ 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 update algorithm takes O (k lg (n + n ′)) worst-case 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 updates to a few structures maintained by our algorithm. Further, by giving a construction, we show it suffices for the algorithm to consider only the case in which the parity of the number of reflex vertices of both ′ and are equal. [ABSTRACT FROM AUTHOR]