Vertex guarding for dynamic orthogonal art galleries
share
Given an orthogonal polygon with orthogonal holes, we devise a dynamic algorithm for guarding with vertex guards, i.e., whenever orthogonal polygon is modified, algorithm updates the set of vertex guards and their positions for guarding the modified orthogonal polygon. Our algorithm modifies the guard placement locally while ensuring the updated orthogonal polygon with h holes and n vertices, is guarded using at most ⌊ (n+2h)/4 ⌋ vertex guards. The algorithm to update vertex guards after any modification to the polygon takes O(k (n+ n')) amortized 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 algorithm takes O(k(n+n')) worst-case time. Initially, we preprocess the input orthogonal polygon with q vertices in O(q q) time to construct data structures of size O(qq/q).
READ FULL TEXT