Member Avatar for thompsonSensibl

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!

  • 3 Contributors
  • 4 Replies
  • 298 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by NormR1
Member Avatar for JamesCherrill

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.

Member Avatar for thompsonSensibl

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 by thompsonSensibl because: n/a
Member Avatar for JamesCherrill

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. :-(

Member Avatar for NormR1

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.