Mapping a polygon with holes using a compass

We consider a simple robot inside a polygon PP with holes. The robot can move between vertices of PP along lines of sight. When sitting at a vertex, the robot observes the vertices visible from its current location, and it can use a compass to measure the angle of the boundary of PP towards north. The robot initially only knows an upper bound n¯ on the total number of vertices of PP. We study the mapping problem in which the robot needs to infer the visibility graph GvisGvis of PP and needs to localize itself within GvisGvis. We show that the robot can always solve this mapping problem. To do this, we show that the minimum base graph of GvisGvis is identical to GvisGvis itself. This proves that the robot can solve the mapping problem, since knowing an upper bound on the number of vertices was previously shown to suffice for computing GvisGvis.