Visibility of Disjoint Polygons

被引：128

作者：

Asano, Takao ^{[1
]}

Asano, Tetsuo ^{[2
]}

Guibas, Leonidas ^{[3
,4
]}

Hershberger, John ^{[3
]}

Imai, Hiroshi ^{[5
]}

机构：

[1] Sophia Univ, Fac Sci & Technol, Tokyo 102, Japan

[2] Osaka Electrocommun Univ, Neyagawa, Osaka 572, Japan

[3] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

[4] DEC Syst Res Ctr, Palo Alto, CA 94301 USA

[5] Univ Tokyo, Fac Engn, Dept Math Engn & Instrumentat Phys, Tokyo 113, Japan

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Computational geometry; Computer graphics; Robotics; Visibility; Hidden-line Elimination; Visibility graph; Shortest path;

D O I：

10.1007/BF01840436

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n(2)) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n(2)) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n(2)) time, improving earlier O(n(2) log n) results.

引用

页码：49 / 63

页数：15

共 18 条

[1]

Asano T., 1985, Transactions of the Institute of Electronics and Communication Engineers of Japan, Section E (English), VE68, P557

[2]

Brown K.Q., 1980, THESIS CARNEGIE MELL

[3] THE POWER OF GEOMETRIC DUALITY [J].

CHAZELLE, B ;

GUIBAS, LJ ;

LEE, DT .

BIT, 1985, 25 (01) :76-90

[4]

CHAZELLE B, 1983, P 24 ANN S FDN COMP, P122

[5]

EDELSBRUNNER H, 1983, P 24 ANN IEEE S FDN, P83

[6]

EDELSBRUNNER H., 1983, ADV COMPUTING RES, V1, P35

[7] A LINEAR ALGORITHM FOR COMPUTING THE VISIBILITY POLYGON FROM A POINT [J].

ELGINDY, H ;

AVIS, D .

JOURNAL OF ALGORITHMS, 1981, 2 (02) :186-197

[8]

ELGINDY HA, 1984, EFFICIENT ALGO UNPUB

[9]

Gabow H.N., 1983, P 15 ANN ACM S THEOR, P246

[10] A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].

GABOW, HN ;

TARJAN, RE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221

← 1 2 →