主题
Search

美术馆定理


也称为 Chvátal 美术馆定理。如果美术馆的墙壁由 n 条直线线段组成,那么整个美术馆总是可以由放置在角落的 |_n/3_| 名警卫来监控,其中 |_x_|向下取整函数。该定理由 Chvátal (1975) 证明。据推测,一个有 n 堵墙和 h孔洞的美术馆需要 |_(n+h)/3_| 名警卫,这已被 Bjorling-Sachs 和 Souvaine (1991, 1995) 以及 Hoffman 等人 (1991) 证明。

在电视剧《NUMB3RS》第二季第“Obsession”集(2006 年)中,Charlie 在搭建一个建筑模型时提到了美术馆定理。


参见

照明问题, 三角剖分, Voronoi 图

使用 Wolfram|Alpha 探索

参考文献

Bjorling-Sachs, I. 和 Souvaine, D. L. "带孔洞多边形的守卫的紧界限。" Report LCSR-TR-165. New Brunswick, NJ: Lab. Comput. Sci. Res., Rutgers Univ., 1991.Bjorling-Sachs, I. 和 Souvaine, D. L. "带孔洞多边形中警卫放置的有效算法。" Disc. Comput. Geom. 13, 77-109, 1995.Chvátal, V. "平面几何中的组合定理。" J. Combin. Th. 18, 39-41, 1975.de Berg, M.; van Kreveld, M.; Overmars, M.; 和 Schwarzkopf, O. 计算几何:算法与应用,第二版修订版。 柏林:施普林格出版社,第 48 页和 59 页,2000 年。DIMACS 研究与教育机构。“美术馆问题。” http://dimacs.rutgers.edu/~cristofa/Xfiles/art.htmlFisk, S. "Chvátal 守卫定理的简短证明。" J. Combin. Th. Ser. B 24, 374, 1978.Fournier, A. 和 Montuno, D. Y. "三角剖分简单多边形和等价问题。" ACM Trans. Graphics 3, 153-174, 1984.Garey, M. R.; Johnson, D. S.; Preparata, F. P.; 和 Tarjan, R. E. "三角剖分一个简单多边形。" Inform. Process. Lett. 7, 175-179, 1978.Hoffmann, F.; Kaufmann, M.; 和 Kriegel, K. "带孔洞多边形的美术馆定理。" Proc. 32nd Annual IEEE Sympos. Found. Comput. Sci., 39-48, 1991.Honsberger, R. "Chvátal 的美术馆定理。" 第 11 章,载于 数学珍宝 II。 华盛顿特区:美国数学协会,第 104-110 页,1976 年。Kahn, J.; Klawe, M.; 和 Kleitman, D. "传统美术馆需要更少的警卫。" SIAM J. Alg. Disc. Math. 4, 194-206, 1993.Klee, V. "关于 d 维 Voronoi 图的复杂度。" Archiv. Math. 34, 75-80, 1980.O'Rourke, J. 美术馆定理与算法。 纽约:牛津大学出版社,1987 年。O'Rourke, J. §2.3,载于 C 语言计算几何,第二版。 剑桥,英格兰:剑桥大学出版社,1998 年。Stewart, I. "美术馆里需要多少警卫?" Sci. Amer. 270, 118-120, 1994 年 5 月。Tucker, A. "美术馆问题。" Math Horizons 1, 24-26, 1994 年春季。Urrutia, J. "美术馆和照明问题。" 第 22 章,载于 计算几何手册 (编辑 J.-R. Sack 和 J. Urrutia)。阿姆斯特丹,荷兰:北荷兰,第 973-1027 页,2000 年。Wagon, S. "美术馆定理。" §10.3,载于 Mathematica 实践。 纽约:W. H. Freeman,第 333-345 页,1991 年。Wells, D. 企鹅趣味几何词典。 伦敦:企鹅出版社,第 9 页,1991 年。

在 Wolfram|Alpha 中被引用

美术馆定理

如此引用

Weisstein, Eric W. "美术馆定理。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/ArtGalleryTheorem.html

主题分类