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

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.

• I was taught that an acceptible estimator just needed to have `d*(A,B) < d(A,B)`, There are some nicer properties for monotonic heuristics `d*(A,F) < d(A,B)+d*(B,F)` but non monotonic work just fine. Jan 22, 2015 at 14:48

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.