Polygon Exploration with Time-Discrete Vision

Details Polygon Exploration with Time-Discrete Vision Polygon Exploration with Time-Discrete Vision

2008-07-15

arxiv.org/abs/0807.2358v2

Computational Geometry: Theory and Applications, 43 (2010), 148-168

Computer Science

Computational Geometry

28 pages, 17 figures, 2 photographs, 3 tables, Latex. Updated some details (title, figures and text) for final journal revisio

Scientific paper

With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and Nuechter for the subproblem of looking around a corner, but until now has not been considered in an online setting for whole polygonal regions. We give the first algorithmic results for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario: We demonstrate that even for orthoconvex polygons, a competitive strategy can be achieved only for limited aspect ratio A (the ratio of the maximum and minimum edge length of the polygon), i.e., for a given lower bound on the size of an edge; we give a matching upper bound by providing an O(log A)-competitive strategy for simple rectilinear polygons, using the assumption that each edge of the polygon has to be fully visible from some scan point.

Affiliated with

Also associated with

No associations

Rating

Polygon Exploration with Time-Discrete Vision does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polygon Exploration with Time-Discrete Vision, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polygon Exploration with Time-Discrete Vision will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-596108