Guarding art galleries by guarding witnesses (extended abstract)

被引：0

作者：

Chwa, Kyung-Yong ^{[1
]}

Jo, Byung-Cheol ^{[2
]}

Knauer, Christian ^{[3
]}

Moet, Esther ^{[4
]}

Van Oostrum, René ^{[4
]}

Shin, Chan-Su ^{[5
]}

机构：

[1] Department of Computer Science, KAIST, Daejon

[2] Taff System, Co. Ltd, Seoul

[3] Freie Universität Berlin, D-14195 Berlin

[4] Institute of Information and Computing Sciences, Utrecht University, 3508 TB Utrecht

[5] School of Electronics and Information Engineering, Hankuk University of Foreign Studies, Yongin

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2004年 / 3341卷

关键词：

D O I：

10.1007/978-3-540-30551-4_32

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Let P be a simple polygon. We define a witness set W to be a set of points such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. Not all polygons admit a finite witness set. If a finite minimal witness set exists, then it cannot contain any witness in the interior of P; all witnesses must lie on the boundary of P, and there can be at most one witness in the interior of every edge. We give an algorithm to compute a minimum witness set for P in O(n2log n) time, if such a set exists, or to report the non-existence within the same time bounds. © Springer-Verlag 2004.

引用

页码：352 / 363

页数：11

共 12 条

[1]

Chvaal V., A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18, pp. 39-41, (1975)

[2]

O'Rourke J., Art Gallery Theorems and Algorithms, The International Series of Monographs on Computer Science, (1987)

[3]

Shermer T.C., Recent results in art galleries, Proc. IEEE, 80, pp. 1384-1399, (1992)

[4]

Urrutia J., Art gallery and illumination problems. Sack, J.R., Urrutia, J., eds, Handbook of Computational Geometry, pp. 973-1027, (2000)

[5]

Cheong O., Van Oostrum R., The visibility region of points in a simple polygon, Proc. 11th Canad. Comf. Comp. Geom., pp. 87-90, (1999)

[6]

Gewali L., Meng A., Mitchell J.S.B., Ntafos S., Path planning in 0/1/∞ weighted regions with applications, ORSA J. Comput., 2, pp. 253-272, (1990)

[7]

Yang T.C., Shin C.S., Guard sufficiency set for polygons, Journal of Korean Information Science and Technology, 28, pp. 73-79, (2001)

[8]

Chwa K.Y., Jo B.C., Knauer C., Moet E., Van Oostrum R., Shin C.S., Guarding Art Galleries by Guarding Witnesses, (2003)

[9]

Bentley J.L., Ottmann T.A., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., C-28, pp. 643-647, (1979)

[10]

Joe B., Simpson R.B., Correction to Lee's visibility polygon algorithm, BIT, 27, pp. 458-473, (1987)

← 1 2 →