# A Heuristic Approach to Calculating Geometric Centers

I was recently tasked with the following problem:

Given a set of points in space, find a point that minimizes the net cost of traveling from to each other point.

Ignoring the problem of calculating costTraveling by car, bike, or foot introduces obvious (and important) time differences. Here, we’ll employ Euclidean distance as an uncomplicated cost function. , this problem may seem fairly straightforward. Let’s look at some approaches.

## 0: as the Median

As it happens, the median of a set of points is guaranteed to be the
cost-minimum center of those points **only in
space**. We can prove this via counter-example: create a triangle
with vertices , the median of which is
at :

The net cost of traveling from the vertices to the center point can be improved by if we make that center point .

For most, isn’t all that much, and the median is a
pretty good approximation for the latter point - the **geometric center**
Also known as the
*geometric median*. ,
or **center** as I will refer to it from here. But what if the margin grows
higher, to or or
? How do we get to that obscure
value?

## 1: Function Minimization

What if we attempt to minimize the net cost function? Of course, first we have to define that function. We can say that for some point , the net cost of traveling from a set of points with coordinate form to is

Note that this function does _not* have the same minimum as - that minimum is the _median*.

Hey, pretty good! Let’s do , , throw in a second derivative test, and call it a day.

Oh man. Maybe not. That looks like a pain in the ass to solve for
, let alone simultaneously with
I have
no idea how to do this efficiently, but if you do, please
let me know. Looks like it could be worth a
**lot** of money . . Don’t forget this process would have to be
automated, too - *wow* that looks fun!

## 2: Heuristic Approximation

You know the old saying:

I may be missing a couple of words, but you get the gist.

If you can’t derive ‘em, approximate ‘em!

…and so heuristics come to the rescue! How? Well, a good place to always start is a contoured version of the function whose extrema are in question.

As expected, the contour slopes in around the previously-shown minimum
. Interestingly, there seems to only be one
minimum for this function - and in general, ** there is** only one
centerSee
this paper, which
shows that the geometric center is unique and convergent for any set of
non-co-linear points. for any set of points! This means we can employ
some descent-type optimization method.

Okay, but where do we descend from?

A convenient place would be from the median. It’s cheap to compute and fairly close to the center, so let’s go with that.

How do we descend?

This is a bit trickier. Of course, we can only travel in
, so let’s just say we can go up, down,
left, or rightFormally, `+y`

, `-y`

, `-x`

, or
`+x`

. A more precise algorithm could also employ diagonal directions. .
To find the best direction of descent, we compute the cost of traveling in each
direction and employ the cheapest one.

What if there’s no direction of improvement?

Then we’ve found our center! Except we could probably do better, by decreasing our search radius and repeating the descent mechanism again. And again. And again, until the approximation of the geometric center is within some acceptable margin of error .

Alright, let’s code it!These examples are in `Rust`

,
but it should be easy to implement the logic in any language of your choice. The
full code can be found here, with a `C++`

version here.
First, the boilerplate - a cost function that takes an array of points, a
center point, and calculates the net distance from the center to each other
point.

And now, we can use the specification previously defined to write a complete algorithm.

Let’s plug in our three points from before, and…

`[0.21126302083333331, 0.21126302083333331]`

Awesome!

## n: Some Details

This function runs in timeA method for near-perfect computation of the geometric center in near-linear is proposed here. , and its precision can be improved by reducing (epsilon) to an arbitrary minimum.