Guarding in a simple polygon

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 m...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2000-09, Vol.75 (4), p.153-158
Main Authors: Lu, Bor-Kuan, Hsu, Fang-Rong, Tang, Chuan Yi
Format: Article
Language:English
Subjects:
Algorithms
Art galleries & museums
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph algorithms
Graph theory
Graphs
Mathematics
Optimization
Sciences and techniques of general use
Simple polygon
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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α(n)) and the longest guard chord in O(n) time of a simple polygon P with n vertices, where α(n) is the inverse of Ackermann's function.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(00)00100-9