Mathematically correct A* heuristic / distance estimator for a latitude / longitude graph

Question

I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates.

Correct ways to calculate the distance between two such points could be the Haversine Formula for spherical earth models, or Vincenty's inverse problem for spheroidal earth models.

But these are very costly in terms of computational resources, and in A* basically you don't need the absolute values of those results, you only need them for comparison purposes.

In my A* algorithm the heuristic function is the shortest distance between 2 points (defined as the length of the smaller great circle arc between the 2 points in a spherical model), and the actual path between two nodes is a linestring, whose length is calculated basically in the same way, just that you sum distances between consecutive vertices.

So, if d(A, B) is the actual geographical distance between A and B (as latitude / longitude points), the problem basically is to find the most computationally efficient distance estimator d*(A, B) that satisfies conditions needed for A* to work properly, such as:

• if d(A, B) < d(C, D) then d*(A, B) < d*(C, D).
• if d(A, B) + d(E, F) < d(C, D) then d*(A, B) + d*(E, F) < d*(C, D)

I even saw in some places that people recommend Euclidean distance for such a case, even though latitude / longitude are angles. It may be the case, but I'm interested if it's "mathematically correct" to assume that it satisfies conditions such as above.

Answer 1

If the area where the nodes can be is small (relatively, the size of half the US is small enough) and away from the poles then you can reasonably approach the problem using just the longitude and latitude as X/Y coordinates. Near the poles you can treat them as polar coordinates with the 90°-latitude as the distance from center and the longitude as the angle from the x-axis.

If you are working across the globe you can transform the lat/lon into a point on a 3D unit sphere, then take the euclidean distance between them. The length of the chord between the 2 points. (2 sin and cos for each coordinate (precomputed), plus a square root). This is however poorly conditioned when the points are close together. Another option instead of the euclid distance is to get the dot product between them and find the acos of it. This will result in the angle between the points.