Suppose we do not have a map of the world but we can fly from a random point towards a random direction. The speed are the same for all flights and remain constant throughout each flight. We do not know the starting coordinate, nor which direction we are going in. However, the territories are conveniently flagged so that through out the flight:
- We know which territory we are in at the start (but not the exact location within that territory),
- We know what the next territory is when we fly across a border, and
- We know how long it takes for us to get from one territory to the next. Alternatively, we could also use distance to the next territory instead.
I am looking for a rigorous treatment of the following:
Given enough samples of flight paths, each starting at a random point and traveling in a straight line in a random direction, is it possible to derive the map showing all of the territories and their borders (up to rotations?)?
Furthermore, if the answer to the above is positive, how would we go about actually deriving the map?
I am imagining a set of flight paths that form a radar scan sweeping from one point and going in circles. Each path puts a dot whenever it crosses a border, and the map can be generated by connecting these dots. If some section of the scan is missing or too coarse, we simply require more samples.
However, no matter how large the sample size is, there may still be a territory where its border "dips" into a neighbouring territory in such a way that our current set of samples skipped over them.
So my initial answer is no; given large but finite sample of paths, we still cannot arrive at the map.
However, we should still be able to come up with a good approximation.
- If a territory is allowed to be a disjunction, fully contained inside another territory, or non-convex, will this affect our goal?
- Is there a class of maps which are inherently more difficult to map compared to the rest? For this, I am thinking of some kind of tessellation, perhaps.