Computing the Visibility Polygon of an Island in a Polygonal Domain

详细信息    查看全文

• 作者：Danny Z. Chen ; Haitao Wang
• 关键词：Visibility polygons ; Polygonal domains ; Polygon with holes ; Algorithms ; Computational geometry
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：77
• 期：1
• 页码：40-64
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

Given a set \({\mathcal {P}}\) of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane, we study the problem of computing the (weak) visibility polygon from a polygonal obstacle \(P^*\) (an island) in \({\mathcal {P}}\). The problem was previously solved in \(O(n^4)\) time, which has been proved worst-case optimal. However, since h may be much smaller than n, it is desirable to have an algorithm whose running time is also a function of h. In this paper, we present such an algorithm of \(O(n^2h^2)\) time, and our algorithm improves the previous result when \(h=o(n)\). In addition, when all obstacles in \({\mathcal {P}}\) (including \(P^*\)) are convex, our algorithm runs in \(O(n+h^4)\) time.