THE ROBOT LOCALIZATION PROBLEM

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 p roblem arises in the localization of robots equipped with a range find er and a compass-P is a map of a known environment, V is the portion v isible from the robot's position, and the robot must use this informat ion to determine its position in the map. We give a scheme that prepro cesses 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 ti me and the preprocessing time and space. In the process of solving thi s problem, we also devise a data structure for output-sensitive determ ination of the visibility polygon of a query point inside a polygon p. We then consider a variant of the localization problem in which there is a maximum distance to which the robot can ''see''-this is motivate d by practical considerations, and we outline a similar solution for t his case. We finally show that a single localization query V can be an swered in time O(mn) with no preprocessing.