Characterizing and recognizing LR-visibility polygons
Characterizing and recognizing LR-visibility polygons
复制标题
表征和识别 LR 可见性多边形
DOI：
10.1016/j.dam.2012.10.030
复制
发表时间：
2014-03
影响因子：
1.1
通讯作者：
蒋波
中科院分区：
文献类型：
--
作者：
蒋波
一个简单多边形P是LR-可见的，如果在P的边界上有两个点s，t，使得P从s到t的顺时针边界上的每个点从P从t到s的另一个边界的某个点可见，反之亦然。我们证明了P不是LR-可见的当且仅当它有k个非冗余分支，使得每个分支都与k′个其他分支精确相交，其中0≤ k′≤ k− 3。我们的表征是通过调查所考虑的非冗余组件的结构，并表示它由一组有向弦的圆。此外，我们开发了一个简单的O（n）时间算法，用于确定是否一个给定的多边形与n个顶点是LR-可见的，以及报告一对或所有对（s，t），承认LR-可见性。这大大简化了现有的识别LR可见多边形的算法。此外，我们的结果可以用来简化现有的解决方案的其他L R-可见性问题。
A simple polygon P is L R-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is visible from some point of the other boundary of P from t to s and vice versa. We show that P is not L R-visible if and only if it has k non-redundant components such that each of them exactly intersects with k′ other components, where 0≤ k′≤ k− 3. Our characterization is obtained by investigating the structure of the considered non-redundant components and representing it by a set of directed chords of a circle. Furthermore, we develop a simple O (n) time algorithm for determining whether a given polygon with n vertices is L R-visible as well as for reporting a pair or all pairs (s, t) which admit L R-visibility. This greatly simplifies the existing algorithm for recognizing L R-visibility polygons. Also, our result can be used to simplify the existing solutions of other L R-visibility problems.
登录
查看更多内容
DOI：
10.1137/s0097539799348670
发表时间：
2002-02
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Frank Hoffmann;Christian Icking;R. Klein;K. Kriegel
通讯作者：
Frank Hoffmann;Christian Icking;R. Klein;K. Kriegel
DOI：
10.1137/s0097539702419352
发表时间：
1999-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Christian Icking;R. Klein;E. Langetepe;S. Schuierer;Ines Semrau
通讯作者：
Christian Icking;R. Klein;E. Langetepe;S. Schuierer;Ines Semrau
DOI：
10.1145/160985.161163
发表时间：
1993-07
期刊：
Int. J. Comput. Geom. Appl.
影响因子：
--
作者：
P. Heffernan
通讯作者：
P. Heffernan
DOI：
10.1016/j.dam.2010.10.007
发表时间：
2011-09
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Bo Jiang;X. Tan
通讯作者：
Bo Jiang;X. Tan
DOI：
10.1016/j.comgeo.2007.04.001
发表时间：
2008-05
期刊：
Comput. Geom.
影响因子：
--
作者：
X. Tan
通讯作者：
X. Tan