What's the "median" of a list of points P = { P1, P2, P3 ... Pn } in more than one dimension? (See the note about typography.) Here are two ideas. Both start by defining a function of any given point x in the space, and both take vector differences between x and each Pi.

Sum of unit vectors. Turn each difference vector into a unit vector by dividing by its length, except where the difference is zero:

u( x ) = sum for all p in P {
0 if x = p
( x - p )
| x - p |
otherwise
}
Here the median is wherever u( x ) is zero (or "crosses" zero at a discontinuity). My friend Richard Harter looked at that definition and suggested this one:

Sum of absolute values. Sum the lengths of the difference vectors:

a( x ) = sum for all p in P { | x - p | }

Here the median is the point where a( x ) is at a minimum.

This browser does not have a Java Plug-in.
Get the latest Java Plug-in here.

Actually both methods can give multiple answers, and we need a way to resolve that. But more interesting to me, both methods tend to give the same answer, although one looks at only the directions of the difference vectors, and the other looks only at their lengths! I think what's going on is that u( x ) is something like the derivative (combination of partial derivatives?) of a( x ), so that a solution of u() corresponds to a minimum of a().

The applet above illustrates both methods. Black dots are input points. The white diamond is the median. A black dot with white inside it is an input point that is also the median. The magnified view helps check whether the median is right on a black point or just near it. The hue of the colors represents the direction of the u() function, and the concentric rings are contours of the a() function.

Click the picture to generate another random set of input points.

Source code: HarterMedian.pde, in Processing, a dialect of Java that simplifies the writing of applets like this.

--Steve Witham


Note about typography

Boldface letters like x stand for vectors or points; Capital P is a list (vector) of points (vectors, argh); Pi means the ith point in the list (not the ith component of a point); and the boldface function u() is a vector-valued function, whereas a( x ) is a scalar-valued function of a point.


version history
0.6: Added Richard Harter's definition.
More mathy.
Stop using the CPU once the picture is drawn.
Generate another picture when clicked.
0.5: First version.