Weak Visibility Queries of Line Segments in Simple Polygons

被引：0

作者：

Chen, Danny Z. ^{[2
]}

Wang, Haitao ^{[1
]}

机构：

[1] Utah State Univ, Dept Comp Sci, Logan, UT 84322 USA

[2] Univ Notre Dame, Dept Comp Sci & Engn, Notre Dame, IN 46556 USA

来源：

ALGORITHMS AND COMPUTATION, ISAAC 2012 | 2012年 / 7676卷

关键词：

TRIANGULATED SIMPLE POLYGONS; ALGORITHMS; PLANE; RAY;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a simple polygon in the plane, we study the problem of computing the weak visibility polygon from any query line segment in the polygon. This is a basic problem in computational geometry and has been studied extensively before. In this paper, we present new algorithms and data structures that improve the previous results.

引用

页码：609 / 618

页数：10

共 14 条

[1] Visibility queries and maintenance in simple polygons
Aronov, B
Guibas, LJ
Teichmann, M
Zhang, L
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2002, 27 (04) : 461 - 483
[2] BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432
[3] Efficient visibility queries in simple polygons
Bose, P
Lubiw, A
Munro, JI
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 23 (03): : 313 - 335
[4] Bygi M., 2011, P 23 CAN C COMP GEOM
[5] AN OPTIMAL ALGORITHM FOR INTERSECTING LINE SEGMENTS IN THE PLANE
CHAZELLE, B
EDELSBRUNNER, H
[J]. JOURNAL OF THE ACM, 1992, 39 (01) : 1 - 54
[6] RAY SHOOTING IN POLYGONS USING GEODESIC TRIANGULATIONS
CHAZELLE, B
EDELSBRUNNER, H
GRIGNI, M
GUIBAS, L
HERSHBERGER, J
SHARIR, M
SNOEYINK, J
[J]. ALGORITHMICA, 1994, 12 (01) : 54 - 68
[7] De Berg M., 2008, Computational Geometry: Algorithms and Applications, V17
[8] ARRANGEMENTS OF CURVES IN THE PLANE TOPOLOGY, COMBINATORICS, AND ALGORITHMS
EDELSBRUNNER, H
GUIBAS, L
PACH, J
POLLACK, R
SEIDEL, R
SHARIR, M
[J]. THEORETICAL COMPUTER SCIENCE, 1992, 92 (02) : 319 - 336
[9] OPTIMAL POINT LOCATION IN A MONOTONE SUBDIVISION
EDELSBRUNNER, H
GUIBAS, LJ
STOLFI, J
[J]. SIAM JOURNAL ON COMPUTING, 1986, 15 (02) : 317 - 340
[10] 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

← 1 2 →