Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
We consider the following problem: given a simple polygon V and a star-shaped polygon V, find a point (or the set of points) in T from which the portion of V that is visible is congruent to V. The problem arises in the localization of robots using a range-finder - V 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 V 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 V, and A is the number of points in V that are valid answers (the output size). Our technique allows us to trade off smoothly between the query time and the preprocessing time or space. We also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon V. 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 also show that a single localization query V can be answered in time O(mn) with no preprocessing.
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Ravi Kumar, Jasmine Novak, et al.
World Wide Web
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Chuang Gan, Boqing Gong, et al.
CVPR 2018