A study on the algorithms for searching a static or moving target in a polygonal region

多边形区域静动目标搜索算法研究

• 批准号: 17500011
• 负责人: TAN Xuehou
• 金额: $ 1.5万
• 依托单位: Tokai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500011/
• 关键词: algorithms; computational geometry; watchman route problem; polygon search problem; on-line algorithms; competitive factor; chain guards; complexity; 時間計算量; 捜索アルゴリズム; 可視イベント; ツーガード問題; 近似アルゴリズム; リンク距離

We presented a new, on-line strategy for a mobile robot to explore an unknown polygon P. starting at a boundary point, which outputs a so-called watchman mute such that every interior point of P is visible from at least one point along the route. The length of the robot's route is guranteed to be at roost 6.7 times that of the shortest watchman route that cnuld be computed off-line. This gives a significant improvement-upon the previously known 26.5-competitive strategy.For the polygon search problem, we also developed an efficient algorithm. Given a simple polygon P with two vertices u and v, the three-guard problem asks whether three guards can move from u to v such that the first and third guards are separately on two boundary chains of P from u to v, and the second guard is always kept to be visible from two other guards inside P. We can decide whether there exists a solution fir the three-guard problem in O(n log n) time, and ifso, generate a walk in O(n log n+in) time, where n denotes the number of vertices of P and m(≦(n^2)) the size of the optimal walk. This improves upon the previous time bounds O(n^2) and O(n^2 log n), respectively.

我们提出了一种新的，在线的策略，移动的机器人探索一个未知的多边形P。从边界点开始，输出一个所谓的守望者静音，使P的每个内部点是可见的，从至少一个点沿着路线。机器人的路径长度保证为离线计算的最短看守路径长度的6.7倍。对于多边形搜索问题，我们也提出了一个有效的算法。给定一个具有两个顶点u和v的简单多边形P，三守卫问题询问三个守卫是否可以从u移动到v，使得第一个和第三个守卫分别位于P从u到v的两个边界链上，并且第二个守卫总是保持从P内部的其他两个守卫可见。我们可以在O（n log n）时间内决定三守卫问题是否存在解，如果是，在O（n log n+in）时间内生成一个遍历，其中n表示P的顶点数，m（n（n^2））是最优遍历的大小。时间复杂度为O（n^2），时间复杂度为O（n^2 log n）

项目成果

An optimal algorithm for the 1-searchability of polygonal rooms

多边形房间1-可搜索性的优化算法

• 发表时间: 2005
• 期刊: Lecture Notes in Computer Science 3742
• 作者: Xuehou;Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan
• 通讯作者: Xuehou Tan

Sweeping simple polygons with the minimum number of chain guards

• DOI: 10.1016/j.ipl.2006.11.010
• 发表时间: 2007-04
• 期刊: Inf. Process. Lett.
• 作者: X. Tan

A new competitive algorithm for exploring unknown polygons

探索未知多边形的新竞争算法

• 发表时间: 2008
• 作者: Xuehou;Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;譚 学厚
• 通讯作者: 譚 学厚

A 2-approximation algorithm for the zookeeper' s route problem

一种解决 Zookeeper 路径问题的 2 逼近算法

• 发表时间: 2006
• 期刊: Information Processing Letters 100
• 作者: Xuehou;Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan
• 通讯作者: Xuehou Tan

A new competitive algorith for exploring unknow polygons

探索未知多边形的新竞争算法

• 发表时间: 2008
• 作者: Xuehou;Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;Xuehou Tan;譚 学厚;潭 学厚
• 通讯作者: 潭 学厚