The robot localization problem

We consider the following problem: given a simple polygon script P signand a star-shaped polygon script V sign, find a point (or the set of points) in script P sign from which the portion of script P sign that is visible is translation-congruent to script V sign. The problem arises in the localization of robots equipped with a range finder and a compass - script P sign is a map of a known environment, script V sign 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 script P sign so that any subsequent query script V sign is answered in optimal time O(m+log n+A), where m and n are the number of vertices in script V sign and script P sign and script A sign is the number of points in script P sign that are valid answers (the output size). Our technique uses O(n5) 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 determination of the visibility polygon of a query point inside a polygon script P sign. We then consider a variant of the localization problem in which there is a maximum distance to which the robot can "see" - this is motivated by practical considerations, and we outline a similar solution for this case. We finally show that a single localization query script V sign can be answered in time O(mn) with no preprocessing.