Hi there,

I am stuck with a problem, and don't know where to start.

I am given a series of cities, and their locations in longitude and latitude. The goal is to find the two cities with the shortest distance.

I have an algorithm which, given the geographical locations (longitude and latitude) of two cities, calculates the distance between them in kilometres.

I also have an algorithm that can calculate the answer in nlogn time, but only with inputs of x,y coordinates, and NOT longitude / latutude :( ...


How could I change longitude,latitude to x,y, in order to use the algorithm and find the closest pairs?

Thank you!

Long/lat map points on a sphere. x,y map points on plane. You can't meaningfully convert between the two except over areas small enough that you can ignore the curvature of the earth.

Long/lat map points on a sphere. x,y map points on plane. You can't meaningfully convert between the two except over areas small enough that you can ignore the curvature of the earth.

Um... here is something that might say otherwise:
http://stackoverflow.com/questions/7129482/closest-pair-of-points-problem
"...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."

but i don't understand the explanation :X any help to understand it would be grateful, thanks!

Edited 5 Years Ago by thompsonSensibl: n/a

No, there's no contradiction. That link proposes converting to 3-dimensional coords (x,y,z) which is OK. I was answering the question about 2-D coordinates (x,y).
I looked at the divide & conquer link, and I didn't understand it either. :-(

Mercator had this problem with his maps.
When you convert lat/long to x,y,z the distance between the points would be though the surface of the earth vs on the surface via a great circle route. No idea if you would get the same results.

I also have an algorithm that can calculate the answer in nlogn time, but only with inputs of x,y coordinates,

how does that algorithm work? Does it use the Pythagorean theorem to compute distances between two x,y points? Can you replace the distance calc with the great circle calc

This article has been dead for over six months. Start a new discussion instead.