In this paper, we consider the problem of computing the region visible to a query pointlocated in a given polygonal domain. The polygonal domain is specified by a simple polygonwith m holes and a total of n vertices. We provide two bounds on the complexity of thisproblem. One approach constructs a data structure with space complexity 0(n2) in time0(0~2lgn) and yields a query time of 0((1 + min(m, |V (q)|))lg~2n + m IV q)|).Here,q)represents the set of vertices of the visibility polygon of a query point q, and 1E1 denotesthe number of edges in the visibility graph. The other approach provides a data structurewith space complexity 0(min(|E|, mn) + n) in time 0(T +1E1+ nlgn) with the query timeof 0(|V(q)|Ign + m). Here, T is the time to triangulate the given polygonal region (whichis 0 (n + m1g1+∈ m) for a small positive constant ∈ > 0).In both of these approaches, 0(m)additive factor in the query time is eliminated with an additional 0((min(IEI,mn))2) spaceand an additional 0(m(min(|E|, mn))~2) preprocessing time.
展开▼
机译：在本文中，我们考虑了计算位于给定多边形域中的查询点可见区域的问题。多边形域由具有m个孔和总共n个顶点的简单多边形指定。对于这个问题的复杂性，我们提供了两个界限。一种方法是在time0（0〜2lgn）中构造空间复杂度为0（n2）的数据结构，并产生查询时间0（（1 + min（m，| V（q）|））lg〜2n + m IV q ）|）。这里，q）表示查询点q的可见性多边形的顶点集，而1E1表示可见性图中的边数。另一种方法是在查询时间为0（| V（q）| Ign + m）的时间0（T + 1E1 + nlgn）中提供空间复杂度为0（min（| E |，mn）+ n）的数据结构。在此，T是对给定的多边形区域进行三角剖分的时间（对于小的正常数ε> 0，它是0（n + m1g1 +∈m））。在这两种方法中，都消除了查询时间中的0（m）可加因数具有额外的0（（min（IEI，mn））2）空间和额外的0（m（min（| E |，mn））〜2）预处理时间。
展开▼
