LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM

被引：3

作者：

Lingas, Andrzej ^{[1
]}

Wasylewicz, Agnieszka ^{[2
]}

Zylinski, Pawel ^{[3
]}

机构：

[1] Lund Univ, Dept Comp Sci, S-22100 Lund, Sweden

[2] Univ Oslo, Dept Math, N-0371 Oslo, Norway

[3] Univ Gdansk, Inst Informat, PL-80952 Gdansk, Poland

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2012年 / 22卷 / 02期

关键词：

Approximation algorithms; r-star cover; orthogonal polygon; POLYGON DECOMPOSITION; ORTHOGONAL POLYGONS; HARD;

D O I：

10.1142/S021819591250001X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has (O) over tilde (n(17))-time complexity, where (O) over tilde (.) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons.

引用

页码：103 / 141

页数：39

共 20 条

[1]

[Anonymous], 1984, THESIS J HOPKINS U

[2]

Chazelle B., 1979, P 11 ANN ACM S THEOR, P38

[3] COVERING POLYGONS IS HARD [J].

CULBERSON, JC ;

RECKHOW, RA .

JOURNAL OF ALGORITHMS, 1994, 17 (01) :2-44

[4]

CULBERSON JC, 1989, 8906 TR U ALB

[5] STATIONING GUARDS IN RECTILINEAR ART GALLERIES [J].

EDELSBRUNNER, H ;

OROURKE, J ;

WELZL, E .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1984, 27 (02) :167-176

[6]

Franzblau DeborahS., 1984, P 16 ANN ACM S THEOR, P167

[7] ON COVERING ORTHOGONAL POLYGONS WITH STAR-SHAPED POLYGONS [J].

GEWALI, L ;

KEIL, M ;

NTAFOS, S .

INFORMATION SCIENCES, 1992, 65 (1-2) :45-63

[8]

Keil J.M., 1986, P 2 ANN S COMP GEOM, P43, DOI [10.1145/10515.10520, DOI 10.1145/10515.10520]

[9]

Keil JM, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P491, DOI 10.1016/B978-044482537-7/50012-7

[10]

LEVCOPOULOS C, 1987, THESIS LINKOPING U

← 1 2 →