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).
