AN EFFICIENT ALGORITHM FOR GUARD PLACEMENT IN POLYGONS WITH HOLES

被引：33

作者：

BJORLINGSACHS, I ^{[1
]}

SOUVAINE, DL ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1995年 / 13卷 / 01期

关键词：

D O I：

10.1007/BF02574029

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we consider the problem of placing guards to supervise an art gallery with holes. No gallery with n vertices and h holes requires more than Left perpendicular (n + h)/3 right perpendicular guards. For some galleries this number of guards is necessary. We present an algorithm which places the left perpendicular (n + h)/3 right perpendicular guards in O(n2) time.

引用

页码：77 / 109

页数：33

共 9 条

[1] AN EFFICIENT ALGORITHM FOR DECOMPOSING A POLYGON INTO STAR-SHAPED POLYGONS [J].

AVIS, D ;

TOUSSAINT, GT .

PATTERN RECOGNITION, 1981, 13 (06) :395-398

[2]

BJORLINGSACHS I, 1991, OCT MSI STON BROOK W, P17

[3] COMBINATORIAL THEOREM IN PLANE GEOMETRY [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (01) :39-41

[4] SHORT PROOF OF CHVATAL-WATCHMAN THEOREM [J].

FISK, S .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 24 (03) :374-374

[5]

HOFFMAN F, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P39, DOI 10.1109/SFCS.1991.185346

[6]

HOFFMANN F, 1991, OCT C RUTG U

[7]

O'Rourke J., 1987, ART GALLERY PROBLEMS

[8]

TOUSSAINT GT, 1986, SIGNAL PROCESS, V3, P853

[9]

[No title captured]

← 1 →