Bill opens up "Café Finder" on his phone, and it tells him that it will take him 10 minutes to get to his nearest Starbucks to grab a triple-shot frapa-crapa-flat-white, so he decides to walk. 20 minutes later, he arrives at Starbucks, thirstier than expected because he had to walk an extra 10 minutes. Bill is also annoyed because he could have gone to Costa which he knew for a fact would have only taken him 15 minutes to get to by foot.

The reason why "Café Finder" told Bill that Starbucks was 10 minutes away is because it was calculated using Euclidean distance (through the Haversine formula) - how the crow flies, instead of how Bill can actually walk there. Although this is generally good in most circumstances, especially on such a small scale like this, I'm being pedantic in the sense that I would like to provide a more accurate estimate as to how long it will really take.

For "Café Finder" to improve its estimation, I drew out two graphs, plotted the start and end coordinates, and determined that a better estimate would be to travel the horizontal distance and then the vertical distance, instead of moving diagonally.

This led to the formula, which seems to resemble Taxicab geometry to an extent:

$$\left| x_{2} - x_{1} \right | + \left | y_{2} - y_{1} \right|$$

However, when tested this often returns a value too large to be realistic.

An option that comes to mind is using an arbitrary number of points in between the coordinates that the crow must fly to as well in order to skew the route, as if it was wobbling from side to side.

What do you recommend in terms of a middle-ground between the two formulas, can you point me in the right direction?

Please go easy in terms of an explanation - I've completed A-Level Maths, but it doesn't extend any further than there!

  • $\begingroup$ The $l_1$ distance depends on rotation, which is why it overestimates. $\endgroup$
    – copper.hat
    Mar 30, 2016 at 2:12
  • $\begingroup$ @copper.hat Sorry I missed out that I'm using the haversine formula to calculate what I'm calling the eucidlean distance, which should therefore take into account curvature of the earth - I'm not sure what you mean by rotation. $\endgroup$
    – max_
    Mar 30, 2016 at 2:15
  • $\begingroup$ @max_ For distances worth walking in order to get a cup of coffee, the influence of curvature is negligible ... $\endgroup$ Mar 30, 2016 at 2:17
  • $\begingroup$ @CatalinZara For sure, I've simplified some aspects of the app for sake of an explanation, but I'm still trying to provide as good as estimation that is possible which is why it's being taken into account. $\endgroup$
    – max_
    Mar 30, 2016 at 2:19
  • $\begingroup$ @max_: The curvature involved in a café trip is negligible to put it mildly. In fact, you might introduce more numerical noise by using it. (I am kidding!) $\endgroup$
    – copper.hat
    Mar 30, 2016 at 2:19


You must log in to answer this question.

Browse other questions tagged .