How to approximate Euclidean distance on the integer plane, without overflow?

Question

I'm working on a platform that has only integer arithmetic. The application uses geographic information, and I'm representing points by (x, y) coordinates where x and y are distances measured in meters. As an approximation, I want to compute the Euclidean distance between two points. But to do this I have to square distances, and with 32-bit integers, the largest distance I can represent is 32 kilometers. Not good. My needs are more on the order of 1000 kilometers. But I'd like to be able to resolve distances on a scale smaller than 30 meters.

Hence my question: how can I compute Euclidean distance, using only integer arithmetic, without overflow, on distances whose squares don't fit in a single word?

ETA: I would like to be able to compute distances, but I might settle for being able to compare them.

Answer 1

Perhaps comparing the octagonal distance approximation would be sufficient?

Slightly more up to date is this article on fast approximate distance functions.