# KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use euclidean distance instead ?

If not, can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ?

Short answer: No, you will not get the same results.

It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into rectangle and save all data (angles and distances) at the same time.
Haversine formula is prepared to operate on circles, 3D distance on sphere, while Euclidean distance will treat them as 2D points, so the result must differ.

Haversine is one of methods to get actual distance on sphere, to use it on Earth, it is only approximation so in such case I would suggest Vincenty formula.

The errors depend on coordinates given and the distance between points.

Take reference point $A =\{40^{\circ}N, 40^{\circ}E\} = \{40, 40\}$, $B =\{42^{\circ}N, 40^{\circ}E\} = \{42, 40\}$, $C =\{40^{\circ}N, 42^{\circ}E\} = \{40, 42\}$, treating them as $X, Y$ tells that they are equidistant - this is how Euclidean distance would see raw coordinates.

According to Haversine formula distance from $A$ to $B$ is ~$222.4 km$ (~$222,108 km$ Vincenty), distance from $A$ to $C$ is ~$170.4 km$ (~$170,784 km$ Vincenty), so it kinda fails.

The idea with ruler on the map, this gets heavy, it will fail as the above, but it depends on map projection (errors change, some projections save angles, some tries to save distances).

• Can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ? – dimitris93 May 18 '16 at 23:58
• These points are not WGS84 though. Is this true if we converted them to WGS84 ? – dimitris93 May 19 '16 at 11:35
• WGS84 is like this: 32.9285723, 25.2859483 – dimitris93 May 19 '16 at 11:47
• @Shiro so it like does not matter, this is true in whatever system you choose - it will fail. To do what you want the transform that maps 3D sphere (ellipsoid) into 2D saving everything (both distances and angles) is needed. Such transform does not exist. – Evil May 19 '16 at 14:28