Consider the following problem: some taxi company has setup a number of stations across the city. In order to dispatch their calls, they need to know for any point in the city, which station is the closest, so that the taxi can get there as fast as possible. (Of course, we are going to use a very special city in which there are no traffic jams, no red lights or stop signs.)

This is a very natural problem for which taxicab geometry is useful. It should be fairly clear that all we need to do to solve this problem, is to find the locus of points which are equidistant to their two closest taxi stations. These boundaries will tesselate the plane in regions (one for each station) corresponding to the points serviced by the corresponding station.

In the introduction, we saw a simple example using two points. The problem is somewhat more difficult when we get 3 or more points. Actually, it is not clear at all how one might go about constructing this tesselation. Before reading on, you might want to sit down and try to construct this graph for 3 points. You will probably realize that it can be somewhat tedious.

In Euclidean geometry, the corresponding graph (tesselating the plane into regions whose points are closest to a station) is called the Voronoi Diagram, and is widely used in computational geometry and pattern recognition. The purpose of the applet below, is thus to compute the taxicab Voronoi diagram of a set of points. Of course the definition of voronoi diagrams makes perfect sense for any well-defined notion of distance, and there actually is a program, called DUST, computing them in different metrics.
 
In order to achieve this, we will use the so called prairie-fire transformation, although in this context, we could call it the taxicab-frenzy transformation. The idea here is fairly simple. Suppose that from each of the taxi stations, we simultaneously send a huge amount of taxis in all possible directions. Moreover, suppose that none of these taxis backtrack, that is always increase the distance between their original station. Then, the taxicab Voronoi diagram will be exactly the locus of points at which two taxis from different stations first meet.
   

I owe many thanks to Xavier Thibaud for help with this applet. I also used the source code of other applets written by McGill students as tutorials for learning the basics of Java.