论文标题
平面动态多边形障碍之间的可见性多边形和可见性图
Visibility Polygons and Visibility Graphs among Dynamic Polygonal Obstacles in the Plane
论文作者
论文摘要
我们设计了一种算法来维持动态多边形域中任何查询点的可见性多边形，即，由于多边形域已用顶点插入并删除其障碍物，我们更新了存储Query Point Poygon Polygon Polygon Polygon的数据结构。在对初始输入多边形域进行预处理以构建一些数据结构后，我们的算法take o（k（\ lg {| vp _ {\ cal p'}（q）|}（q）|}（q）|}）+（\ lg {n'}） p'}（q）|）+h））更新数据结构的最差时间来存储可见性多边形vp _ {\ cal p'}（q）q的q的q时，当将任何顶点v插入到（从中删除）当前多边形域的任何矩形）时。在这里，n'是\ cal p'中的顶点数，h是\ cal p'中的障碍次数，vp _ {\ cal p'}（q）是q in \ cal p'in \ cal p'的可见性多边形（| vp _ {| vp _ {\ cal p'}（q）|是vp cal is的数量，是vp _ is的数量） VP _ {\ cal p'}（q）的组合变化由于v的插入（rev。estretion）。 作为上述算法的应用，我们还设计了一种用于维持动态多边形结构域的可见性图的算法，即，作为多边形域的插入和障碍物的删除，我们更新了存储多边形域可视性图的数据结构。 After preprocessing the initial input polygonal domain, our dynamic algorithm takes O(k(\lg{n'})^{2}+h) (resp. O(k(\lg{n'})^{2}+h)) worst-case time to update data structures that store the visibility graph when any vertex v is inserted to (resp. deleted from) any obstacle of the当前的多边形域\ cal p'。在这里，n'是\ cal p'中的顶点的数量，h是\ cal p'中的障碍次数，k是\ cal p'可见度图中的组合变化数量，这是由于V的插入（分别删除）。
We devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that store the visibility polygon of the query point. After preprocessing the initial input polygonal domain to build a few data structures, our algorithm takes O(k(\lg{|VP_{\cal P'}(q)|})+(\lg{n'})^{2}+h) (resp. O(k(\lg n')^2+(\lg|VP_{\cal P'}(q)|)+h)) worst-case time to update data structures that store visibility polygon VP_{\cal P'}(q) of a query point q when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain \cal P'. Here, n' is the number of vertices in \cal P', h is the number of obstacles in \cal P', VP_{\cal P'}(q) is the visibility polygon of q in \cal P' (|VP_{\cal P'}(q)| is the number of vertices of VP_{\cal P'}(q)), and k is the number of combinatorial changes in VP_{\cal P'}(q) due to the insertion (resp. deletion) of v. As an application of the above algorithm, we also devise an algorithm for maintaining the visibility graph of a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update data structures that store the visibility graph of the polygonal domain. After preprocessing the initial input polygonal domain, our dynamic algorithm takes O(k(\lg{n'})^{2}+h) (resp. O(k(\lg{n'})^{2}+h)) worst-case time to update data structures that store the visibility graph when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain \cal P'. Here, n' is the number of vertices in \cal P', h is the number of obstacles in \cal P', and k is the number of combinatorial changes in the visibility graph of \cal P' due to the insertion (resp. deletion) of v.
