论文标题
为动态正交美术馆守卫顶点
Vertex Guarding for Dynamic Orthogonal Art Galleries
论文作者
论文摘要
我们设计了一种算法，用于调查动态正交多边形领域，通过将一个警卫放在每个顶点的一个子集中，即每当一个正交多边形域{\ cal p'}都会被修改以在另一个正交多边形domain domain domain {\ certion cournith中进行修改时，每当一个正交多边形域{\ cal p'}。 {\ cal p'}，以便更新的后卫设置调查{\ cal p}。我们的算法修改了O（k \ lg {（n+n'）}）摊销时间中的后卫放置，同时确保使用H孔和n位置的更新的正交多边形结构域，最多可使用\ lfloor（n+2h）/4 \ rfloor vertex Guards守护。对于初始正交多边形的特殊情况，无孔，每次更新导致无孔的正交多边形，我们的后卫更新算法将O（K \ lg {（n+n'）}）最差的时间。在这里，n'和n分别是更新之前和之后正交多边形的顶点的数量。 k是| n -n'|的总和。以及我们算法维护的一些结构的更新数量。此外，通过给出构造，我们证明了算法仅考虑{\ cal p'}和{\ cal p}的反射顶点数量的奇偶校验的情况是相等的。
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 {\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')}) amortized time while ensuring the updated orthogonal polygonal domain 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 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 {\cal P'} and {\cal P} are equal.
