多边形搜索是计算几何中的一类基本问题,这类问题考虑的是如何利用一个或多个移动的搜索者(搜索者有不同的视觉范围)对一个多边形区域进行搜索以便检测到移动的入侵者。搜索者和入侵者均可用一个点表示,都可以在多边形区域内连续、任意地移动,但是后者的移动速度要比前者快。多边形搜索问题与机器人技术相结合被广泛应用于航海,安全防御,目标探测和追踪等诸多领域。因此,对于一个给定的多边形,判断其是否可被一个或多个不同视觉的搜索者搜索,以及如何找出一条有效的搜索路径显得尤为重要。本文主要研究的是用一个边界单线搜索者(1-searcher)对一个含有n条边的简单多边形的搜索问题。所谓边界单线搜索者,是指搜索者只能沿多边形的边界移动且从其位置只能发出一束光。作为一种特殊类型的搜索模型得到了许多学者的研究,虽然已经提出了一些检测和搜索算法,但各个算法还是存在一些不足。本文在对多边形边界单线搜索的研究现状和存在的不足进行深入分析的基础上做了以下工作:首先,阐述了多边形搜索问题的相关概念,并将双切线与多边形的可视图( V图)联系构造了简化骨架V图。其次,针对边界单线搜索问题,给出了检测多边形的边界单线可搜索性的充要条件。利用这些条件判断一个多边形是否可被一个边界单线搜索者搜索只需O(n)的时间和空间,改进了以前的时间复杂度O(nlogn)。此时间复杂度是检测多边形边界单线可搜索性的下界,已不可能再优化。同时,对这些特性的正确性用简化骨架V图论证,简化了已有的证明过程。最后,给出了一种新的边界单线搜索算法,并对此算法进行了详细的描述。同时,证明了用该搜索算法输出一个搜索方案只需O(m)的时间,其中m(< n~2)为搜索指令的数目,优于以前O(nlogn + I) (I < 3n~2)时间的算法。此外,还证明了边界单线搜索者利用此算法搜索多边形所走过的路径最短,最长路径小于2|(?)P|,其中|(?)P|为多边形边长总和。