LR-visibility in polygons

被引：28

作者：

Das, G ^{[1
]}

Heffernan, PJ ^{[1
]}

Narasimhan, G ^{[1
]}

机构：

[1] UNIV MEMPHIS,DEPT MATH SCI,MEMPHIS,TN 38152

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 7卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

polygonal visibility; weak visibility;

D O I：

10.1016/0925-7721(95)00042-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a linear-time algorithm which, for a simple polygon P, computes all pairs of points s and t on P that admit LR-visibility. The points s and t partition P into two subchains. We say that P is LR-visible with respect to s and t if each point of P on the chain from s to t is visible from some point of the chain from t to s and vice-versa.

引用

页码：37 / 57

页数：21

共 17 条

[1] AVIS D, 1981, IEEE T COMPUT, V30, P910, DOI 10.1109/TC.1981.1675729
[2] VISIBILITY AND INTERSECTION PROBLEMS IN PLANE GEOMETRY
CHAZELLE, B
GUIBAS, LJ
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) : 551 - 581
[3] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME
CHAZELLE, B
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) : 485 - 524
[4] Chen D. Z., 1992, Proceedings of the Eighth Annual Symposium on Computational Geometry, P63, DOI 10.1145/142675.142692
[5] CHEN DZ, 1992, 92028 PURD U DEP COM
[6] CHEN DZ, IN PRESS INT J COMPU
[7] DAS G, 1993, UNPUB FINDING ALL WE
[8] AN ALGORITHM FOR DETERMINING VISIBILITY OF A SIMPLE POLYGON FROM AN INTERNAL LINE SEGMENT
DOH, JI
CHWA, KY
[J]. JOURNAL OF ALGORITHMS, 1993, 14 (01) : 139 - 168
[9] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS
GUIBAS, L
HERSHBERGER, J
LEVEN, D
SHARIR, M
TARJAN, RE
[J]. ALGORITHMICA, 1987, 2 (02) : 209 - 233
[10] HEFFERNAN PJ, IN PRESS INT J COMPU

← 1 2 →