Approximate Guarding of Monotone and Rectilinear Polygons

被引：15

作者：

Krohn, Erik A. ^{[1
]}

Nilsson, Bengt J. ^{[2
]}

机构：

[1] Univ Wisconsin, Dept Comp Sci, Oshkosh, WI 54901 USA

[2] Malmo Univ, Dept Comp Sci, S-20506 Malmo, Sweden

来源：

ALGORITHMICA | 2013年 / 66卷 / 03期

关键词：

Computational geometry; Art gallery problems; Monotone polygons; Rectilinear polygons; Approximation algorithms; ART GALLERY PROBLEMS; VISIBILITY POLYGON; ALGORITHM;

D O I：

10.1007/s00453-012-9653-3

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT (2)).

引用

页码：564 / 594

页数：31

共 33 条

[1]

[Anonymous], 1999, HDB COMPUTATIONAL GE

[2]

[Anonymous], 1984, THESIS J HOPKINS U

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[4]

BRODEN B, 2001, P 13 CAN C COMP GEOM, P45

[5]

CARDANO G., 1545, ARTIS MAGNAE SIVE RE

[6]

Chazelle B., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P220, DOI 10.1109/FSCS.1990.89541

[7]

Chen D.Z., 1995, P 7 CANADIAN C COMPU, P133

[8] OPTIMUM WATCHMAN ROUTES [J].

CHIN, WP ;

NTAFOS, S .

INFORMATION PROCESSING LETTERS, 1988, 28 (01) :39-44

[9]

CHVATAL V, 1975, J COMB THEORY B, V13, P395

[10]

CLARKSON KL, 2005, P 21 ACM S COMP GEOM

← 1 2 3 4 →