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:

  1. We know which territory we are in at the start (but not the exact location within that territory),
  2. We know what the next territory is when we fly across a border, and
  3. 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.
  • $\begingroup$ You may also need an assumption about speeds: If there are consistently lower above one territory than another, then this could distort your map $\endgroup$ – Henry Oct 2 '17 at 9:09
  • $\begingroup$ Yup, speed for all of the flights are the same and constant throughout the whole duration of each flight. I will make it more clear. $\endgroup$ – Little Pillow Oct 2 '17 at 9:45
  • $\begingroup$ I think that you should say that your problem has a probabilistic nature: you have a finite number of path samples (line segments, with "tags" on them whenever you cross a boundary) out of which you want to obtain a most likely (in a sense to be defined) map. Connected: I have taken the liberty to modify your tags in order to direct the answerers in a more accurate way, in particular with the tag "computational geometry". $\endgroup$ – Jean Marie Oct 3 '17 at 8:38
  • $\begingroup$ Thank you, I did had a hard time choosing the tags for the question. $\endgroup$ – Little Pillow Oct 3 '17 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.