Optimum sweeps of simple polygons with two guards |
| |
Authors: | Xuehou Tan Bo Jiang |
| |
Affiliation: | 1. School of Information Science and Technology, Tokai University, 4-1-1 Kitakaname, Hiratsuka 259-1292, Japan;2. School of Information Science and Technology, Dalian Maritime University, Linghai Road 1, Dalian, China |
| |
Abstract: | A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n2) time and O(n) space algorithm for optimizing this metric, where n is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n). |
| |
Keywords: | Computational geometry Visibility Ray shooting Polygon sweep problem Two-guard problem |
本文献已被 ScienceDirect 等数据库收录! |
|