主題
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 圖

使用 探索

參考文獻

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 年。

在 中被引用

美術館定理

如此引用

Weisstein, Eric W. "美術館定理。" 來自 網路資源。 https://mathworld.tw/ArtGalleryTheorem.html

主題分類