Blog on Applied Mathematics

Euclidean distance and others: bikers, taxi drivers and the distance definition [Part 1]

bici

In these days I and a collegue of mine had a conversation on a recent law proposed by  Ségolèn Royal in French Parlament.

Shortly, this law would provide a monetary refund for those who go to work by bike; the refund is proportional to the distance covered every day.

After a moment, everyone of us started thinking at the main point of it; everyone knows that there are lots of choices of paths when going from a point A to a point B in a city and everyone knows that the paths have different lengths. Which of those paths is used for deciding the amount of money to be refunded? We agreed on the answer...the shortest one; and you, do you agree with us? Probably someone among my readers doesn't know there are a lot of way to calculate the shortest distance between two points. In this post we will talk about distances, the way used to calculate them and some basic concepts in topology and limits.

The easiest way to calculate the distance between two points is the Euclidean distance. The Euclidean distance is the first we learn at school and the one we are confident to. Imagine an employee that lives in an imaginary point A on a bi-dimensional plane. The company is situated in a point B on the same plane. The best choice to go to work for him is to move straight on from A to B. To draw it, we can fix two different points in the plane and connect them with a stright line: this is the Euclidean distance.

punti_linea

For a more detailed discussion suppose to introduce a reference system with the origin in a certain point O. In the reference system both point A and B would have two coordinates (we are using a bi-dimensional plane, in a three dimensional space such as the Earth there are three coordinates).

coordinate

The formula for Euclidean distance between A and B is

d = \sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}

really easy to figure out.

You are not the only one...

It is well known that the civilization improves and some houses are built on the spece between point A and B.

 blocchi

Our friend, now, has to change the way to go from home to work according to the streets available between the houses.

The employee will pass two houses in vertical direction (up - down direction on your screen) and three houses in horizontal direction (left - right direction) and this the shortest way from home to work and is surely grater than Euclidean distance... a lucky fact for the company who refund the worker.

The distance shown above is called taxi distance or Manhattan distance and is expressed by the following equation

d=|x_{2}-x_{1}|+|y_{2}-y_{1}|

This is a valid alternative to Euclidean distance in everyday life; for example when we drive we use the taxi distance to decide the shortest way to go from our position to the final destination.

 But now we have a problem: in order to save some money, the company establishes to refund only higher distance between the vertical and the horizontal. In the case of our employee only the horizontal distance will be refunded (three houses versus two houses in vertical direction). This could seem a stretch of taxi distance but there is a refined equation to express this distance:

d=max(|x_{2}-x_{1}|,|y_{2}-y_{1}|)

this is called distance of infinity.

At the end, there is another distance we can investigate: the minimum distance. It is obtained changing max with min in the distance of infinity; simply only the shortest distance is kept in account and is written as

d=min(|x_{2}-x_{1}|,|y_{2}-y_{1}|)

As we have seen, there are lots of different distances between two points. We are more familiar with some definitions of distance than others but, each definition given above, is a valid distance in the physical word.

An entirely mathematical definition rises up some questions; What is the best way to measure a distance? How many different distances are there?

We will answer these questions in reverse order. With a little imagination we can suppose that there are infinite ways to define a distance. From a mathematical point of view every equation involving subtractions of coordinates of two points is a distance. After this answer, some of us are starting to have doubts the existence of a universal definition for distances.

It is almost totally true. We cannot define a unique distance definition but we can define some criteria a distance definition must be respect.

Some rules for a good distance

First of all, a distance must be "positive defined"; in mathematical linguage this means that the value of a distance must be greater tha or, at least, equal to zero but never negative. It sounds so intuitive and everyone agrees that a distance between two points must be positive or zero (if the starting point coincides with the arriving one). I want you notice we are not considering vectorial distance that is positive in one direction and negative in the opposite one.

The second criteria is an extension of first one; it underlines that the distance is zero only if the starting point  and the arriving one coincide.

In this case a little deviation is necessary. Suppose our biker travels from his house to another and suppose this new house is in the same street of his company.

errore_min

Now he has to run three blocks in horizontal direction and zero in vertical direction. If we apply the minimum distance the distance from A to B is zero, the biker could get a little angry for this; this is surely not true.So, we notice the minimum distance is not a good definition and cannot be accepted.

Switching back to our criteria; the third is the symmetry of the distance calculation. It can be written as

d(A,B)=d(B,A)

The distance from A to B is the same from B to A and this is intuitive too.

The last criterium is the most important one and is called triangular inequality.

disequazione_triangolare

Suppose our biker, before going to work, needs to leave his son at school; to figure out the scene we suppose the school is in the point C in the above figure. If C is on the path from A to B there is no distance increase and we can write

d(A,B)=d(A,C)+d(C,B)

If the point isn't on the path from A to B (see figure above) the distance from A to C and then from C to B is higher than distance from A to B. In mathematical form it is

d(A,B)<d(A,C)+d(C,B).

Putting all together we obtain the triangular inequality

{d(A,B)}\leq{d(A,C)+d(C,B)}

With the triangular inequality we have completed the criteria and this discussion too. In the next post we will talk about metrical spaces and topology.

No Comments Yet

Leave a Reply

Your email address will not be published. Required fields are marked *