Guarding in a simple polygon

作     者：Lu, BK Hsu, FR Tang, CY 

作者机构：Providence Univ Dept Accounting Taichung 433 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2000年第75卷第4期

页      面：153-158页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：I Support in part by NSC grant NSC-87-2213-E-127007. ∗Corresponding author. E-mail addresses: bklu@cs.nthu.edu.tw (B.-K. Lu)  frhsu@pu. edu.tw (F.-R. Hsu)  cytang@cs.nthu.edu.tw (C.Y. Tang) 

主　　题：simple polygon graph algorithms 

摘      要：Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in O(n) time, the shortest guard diagonal in O(n alpha(n)) and the longest guard chord in O(n) time of a simple polygon P with n vertices, where alpha(n) is the inverse of Ackermann s function. (C) 2000 Elsevier Science B.V. All rights reserved.