The robot localization problem

Abstract

We consider the following problem: given a simple polygon P and a star-shaped polygon V , find a point (or the set of points) in P from which the portion of P that is visible is translation-congruent to V . The problem arises in the localization of robots equipped with a range-finder and a compass --- P is a map of a known environment, V is the portion visible from the robot's position, and the robot must use this information to determine its position in the map. We give a scheme that preprocesses P so that any subsequent query V is answered in optimal time O(m + log n + A), where m and n are the number of vertices in V and P , and A is the number of points in P that are valid answers (the output size). Our technique uses O(n 5 ) space and preprocessing in the worst case; within certain limits, we can trade off smoothly between the query time and the preprocessing time and space. In the process of solving this problem, we also devise a data structure for output-sensitive determinati...