多边形的边界单线搜索特征  

Characterization of Boundary 1-Searcher for Polygons

作　　者：李丽[1] 张远平[1] 李鹏[1] 

机构地区：[1]兰州理工大学计算机与通信学院,中国兰州730050

出　　处：《湖南师范大学自然科学学报》2010年第4期19-24,共6页Journal of Natural Science of Hunan Normal University

基　　金：国家自然科学基金资助项目(61064011)

摘　　要：多边形搜索问题,是在一个多边形区域内搜索一个移动的入侵者,此入侵者的移动路线和速度都是未知的.主要研究一个边界单线搜索者(1-searcher)对简单多边形的搜索问题,给出了检测多边形是否可搜索的充要条件,利用这些条件判断一个多边形的可搜索性只需O(n)的时间和空间,改进了以前的时间复杂度O(nlogn),同时简化了已有的证明过程.The polygon searching is the problem of finding a mobile intruder in a polygonal region where the intruder＇s moving path and moving speed are unpredictable.The problem of searching a simple polygonal region with a boundary 1-searcher is considered,and the necessary and sufficient conditions for testing the searchablity of polygons are proposed.It is showed that if a polygon is searchable by a boundary 1-searcher can be detected in O（n） time and space by using these conditions.The results improve the previous O（nlogn） time bounds.At the same time,some known proving processes are simplified.

关 键 词：多边形搜索 单线搜索 边界搜索 搜索策略 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]