A graph-based approach to the visibility-based pursuit-evasion problem

基于图的方法解决基于可见性的追击躲避问题

• 批准号: 23500024
• 负责人: TAN Xuehou
• 金额: $ 2.83万
• 依托单位: Tokai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500024/
• 关键词: アルゴリズム; 計算幾何; 幾何学的捜索問題; 可視性; ツーガイド問題; LR-可視的多角形; グラフアルゴリズム; 単純経路; 経路探索問題; 幾何学的捜索; グラフ的手法

This work presents a new method for solving the visibility-based pursuit-evasion problems, mainly by transforming them into the shortest path problems in graphs. For the two-guards problem, we presented the O(n^2) time algorithms for computing the search schedules in which the sum of the distances traveled by the two guards is minimized, or the maximum distance between the two guards is minimized. For the problem of searching mobile intruders in a circular corridor by two 1-searchers, we gave an O(n*n) time solution. For the problem of finding a simple path that turns at the points from the given n points but avoids the boundary of the given polygon of m vertices, we presented an O((n*n+m) log m) time algorithm, which greatly improves upon the previous O((n m)*(n m)) time bound. Finally, we also gave a simple characterization of LR-visibility polygons and a linear-time algorithm for determining whether a given polygon is LR-visible.

本文提出了一种新的基于可行性的追逃问题的求解方法，主要是将追逃问题转化为图中的最短路问题。对于两个守卫问题，我们给出了O（n^2）时间算法来计算搜索时间表，其中两个守卫移动的距离之和最小化，或者两个守卫之间的最大距离最小化。对于两个1-搜索器搜索圆形走廊中的移动的入侵者的问题，给出了O（n*n）时间的解.对于从给定的n个点中寻找一条在点处转弯但避开给定的m个顶点的多边形边界的简单路径的问题，我们给出了一个O（（n*n+m）log m）时间的算法，大大改进了以前的O（（n m）*（n m））时间限制.最后，我们还给出了LR可见多边形的一个简单刻画和判定给定多边形是否LR可见的线性时间算法。

项目成果

Characterizing and recognizing LR-visibility polygons

表征和识别 LR 可见性多边形

• DOI: 10.1016/j.dam.2012.10.030
• 发表时间: 2014-03
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: 蒋波

Finding simple paths on given points in a polygonal region

在多边形区域中的给定点上查找简单路径

• 发表时间: 2014
• 期刊: Lect Notes Comput. Sci
• 作者: Takehiro Ito;Yuichiro Miyamoto;Hirotaka Ono;Hisao Tamaki;Ryuhei Uehara;X. Tan and B. Jiang
• 通讯作者: X. Tan and B. Jiang

Minimization of the maximal distance between the two guards patrolling a polygonal region

最小化在多边形区域巡逻的两个警卫之间的最大距离

• 发表时间: 2014
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Xuehou Tan;Bo Jiang
• 通讯作者: Bo Jiang

Minimization of the maximum distance between the two guards patrolling a polygonal region

• DOI: 10.1016/j.tcs.2013.03.019
• 发表时间: 2012-05
• 期刊: Theor. Comput. Sci.
• 作者: X. Tan;Bo Jiang

Searching for mobile intruders in circular corridors by two 1-searchers

• DOI: 10.1016/j.dam.2010.10.007
• 发表时间: 2011-09
• 期刊: Discret. Appl. Math.
• 作者: Bo Jiang;X. Tan