Sunday, February 22, 2009

Distances

What's a distance?

Let's imagine a map spread out on the table, with east/west in one direction and north/south in the other. We can make the grid as fine as we like, pick a center, and say that we measure x to the right and y up from the center. Any point on the map will have a position (x,y), with x measured to the east of the center and y measured to the north. West means negative x and south means negative y.

How far apart are two points on the map?

Someone naive might say: take the difference in x and the difference in y and add them. A sophisticated student would snicker at that: a crow would fly straight straight from one point to the other and only have to travel √ ((x1-x2)^2+(y1-y2)^2) . But the pros know it isn't really a stupid answer at all. It depends.

Suppose the map corresponds to a city with east/west and north-south streets. Maybe a crow can fly diagonally, but the taxicab driver has to follow the streets. If he has to go from 600 West/200 South to 300 West/200 North he has to drive 3 blocks East and 4 blocks North, for a total for 7 blocks. The crow can fly it in only 5, but that doesn't help the cabdriver.

The same map can demand different distances depending on what it represents.

The mathematical term for a set of distances like this is a metric (from the root word for measuring). The rules for a metric space are pretty simple and obvious. It is a set of points where:

  • Every two points have a distance between them
  • The distance is never negative.
  • The only time the distance is 0 is when the two points are the same.
  • The distance between a point and itself is always 0.
  • The distance from A to B is never smaller than the distance from A to C plus the distance from C to B. It might result in the same distance, but a detour in the middle of a trip never makes the trip shorter

The mathematically inclined can verify that both the traditional "as the crow flies" metric and the "taxicab" metric satisfy these conditions. Intuition will serve the rest of us OK. Remember that sets can be infinite: a line is a set of points, but an infinite number of them.

You can easily imagine some other cases where the distance takes funny shapes.

Suppose the map is of a nice flat plain, with a river down the middle and only a couple of bridges. Two points on the map, if on opposite sides of the river, might be very far apart: or very close, depending on where the bridges are.

Or suppose that the map is of the area around a hill. The real distance a traveler experiences is going to involve uphill and downhill aspects. It might well be easier to go around the hill than over it, and the new distance you devise will reflect that.

There's always a distance system called the "trivial metric:" The distance between two points is always 1, unless the two points are the same. It is a handy case for testing theorems, but not much use for anything else. It works--it satisfies the criteria--but it doesn't reflect landscapes we want to work with.

An amusing exercise is to ask: what is a straight line in an arbitrary metric space? Instead of devising some complicated parametric formula, we can say that "The line segment from A to B is the set of all points for which going from A to that point and then from that point to B doesn't make the trip any longer."

The results can be wild.

No comments:

Post a Comment