Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding closest pair of points on a sphere

I know how to implement n log n closest pair of points algorithm (Shamos and Hoey) for 2D cases (x and y). However for a problem where latitude and longitude are given this approach cannot be used. The distance between two points is calculated using the haversine formula.

I would like to know if there is some way to convert these latitudes and longitudes to their respective x and y coordinates and find the closest pair of points, or if there is another technique that can be used to do it.

like image 242
Varun Sharma Avatar asked Aug 20 '11 03:08

Varun Sharma


People also ask

How do you find the points of a sphere?

The general equation of a sphere is: (x - a)² + (y - b)² + (z - c)² = r², where (a, b, c) represents the center of the sphere, r represents the radius, and x, y, and z are the coordinates of the points on the surface of the sphere.

What is the closest pair explain the closest pair algorithm?

In this problem, a set of n points are given on the 2D plane. In this problem, we have to find the pair of points, whose distance is minimum. To solve this problem, we have to divide points into two halves, after that smallest distance between two points is calculated in a recursive way.


1 Answers

I would translate them to three dimensional coordinates and then use the divide and conquer approach using a plane rather than a line. This will definitely work correctly. We can be assured of this because when only examining points on the sphere, the two closest points by arc distance (distance walking over the surface) will also be the two closest by 3-d Cartesian distance. This will have running time O(nlogn).

To translate to 3-d coordinates, the easiest way is to make (0,0,0) the center of the earth and then your coordinates are (cos(lat)*cos(lon),cos(lat)*sin(lan),sin(lat)). For those purposes I'm using a scale for which the radius of the Earth is 1 in order to simplify calculations. If you want distance in some other unit, just multiply all quantities by the radius of the Earth when measured in that unit.

I should note that all this assumes that the earth is a sphere. It's not exactly one and points may actually have altitude as well, so these answers won't really be completely exact, but they will be very close to correct in almost every case.

like image 64
Keith Irwin Avatar answered Oct 09 '22 10:10

Keith Irwin