A new competitive strategy for exploring unknown polygons (アルゴリズム)

概要

論文の詳細を見る
We present a new, on-line strategy for a mobile robot to explore an unknown simple polygon, starting at a boundary point s, which outputs a so-called watchman route 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 guaranteed to be at most 4√2+1⪇6.7 times that of the shortest watchman route that could be computed off-line. This gives a significant improvement upon the previous 26.5-competitive strategy, which was presented by Hoffmann et al. [?]. A novelty of our competitive strategy is a recursive procedure that reduces the polygon exploration problem to the subproblems of exploring two different types of reflex vertices. Moreover, our analysis of the competitive factor for a subproblem is based on the off-line √2-approximation algorithm for the watchman route problem [?] and a geometric structure called the angle hull [?].
一般社団法人情報処理学会の論文
2008-01-18