Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have n points and a way to measure the pairwise (probably non-Euclidean) distance between them. I would like to have some way to measure the total "closeness" of my points, but I'm not really sure of the best way to do that.

First of all, I could see approaching this from some sort of analytical or topological angle (since I suppose I really do have a metric space) or from a graph theory perspective (I could consider each element a node of the complete weighted graph on n vertices such that the weight aligns with the distance between nodes). I'm leaning towards a graph theory approach but I can't articulate why.

One obvious approach that comes to mind is to simply take the sum of all pairwise distances. I don't know why, but that just seems too simple.

Another approach would be to find the minimal distance to traverse all nodes in the traveling salesperson sense. This might best align with an intuitive notion of closeness, but it obviously becomes intractable beyond a very small number of nodes (although in my case I happen to be dealing with a small number of nodes anyway).

A compromise on the TSP path length would perhaps be to find the weight of a minimal spanning tree. That should be performant and still somewhat intuitive, so it's probably the leading candidate right now.

Is there a standard approach to this thing that I am unaware of? Am I overlooking any better technique here?

As an aside, I'm curious whether or not the triangle inequality is necessary (since I'm not 100% sure that the distance metric I want really is a distance metric).

EDIT: I forgot to mention this, but my space need not have anything to do with $\mathbb R^{n}$, and indeed in the case I have in mind the space is finite.

share|improve this question
    
Michael: Judging by your edit it seems that you think my answer was intended to the Euclidean metric on finite dimensional real vector spaces. I assure you, however, that it fits every metric space. I have added the relevant point to my answer. –  Asaf Karagila Sep 20 '11 at 22:56
    
@AsafKaragila Yeah I know; I read your answer too quickly and confused myself. I realized my confusion before your edit, but the I thought I'd let my edit stand. –  Michael McGowan Sep 21 '11 at 0:50

2 Answers 2

up vote 4 down vote accepted

Suppose your nodes are $x_1,\ldots, x_n$ in the space $X$

How about the least radius encompassing all the points? We can define this as: $$\inf\{r\in\mathbb R^{\ge0}\mid\exists x\in X\forall k\le n\colon x_k\in B(x,r)\}$$

Where $B(x,r)$ is the open ball with center $x$ and radius $r$. Alternatively you may want to choose the closed ball.

This definition is not limited to $\mathbb R^n$, nor it is to the Euclidean metric. Every metric is defined as a function into $\mathbb R^{\ge 0}$, and every metric space would have some points $x$ and a radius $r$ such that $x_i\in B(x,r)$ for all $i$. Of course if the space is exactly our nodes, this definition is somewhat moot. If however there are more points, then this may still be useful.

share|improve this answer
    
The approach above is indeed a topological one, by the way. –  Asaf Karagila Sep 20 '11 at 23:32

Here are some other suggestions:

  • The maximum distance of two points.
  • Every other vector norm of the vector of pairwise distances.
  • The sum of the distances of every point to the "center of gravity" of the points (which would need some linear structure on the space of points).
  • Similar as above but with some other point which is "in the middle of all points", e.g. the center of the smallest ball which encloses all points (as in Asaf's answer).
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.