I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I define as the point with the minimum sum of distances to all other points. The metric computation is slow, so needs to be avoided where possible.
The obvious way to find this point uses $n^2$ metric distance calculations, as it simply (a) calculates for each point the sum of distances to all other points and then (b) takes the minimum point.
Is there a way to do this in less than $O(n^2)$ distance comparisons? (Probably making use of the triangle inequality in some way, which should hold with my metric.)
A good approximation might suffice if an exact method doesn't exist.
Asked By : Open Door Logistics
Answered By : D.W.
No. You can't do better than $\Theta(n^2)$ in the worst case.
Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of that edge to be either $0.9$, $1.0$, or $1.1$; all of those choices are consistent with all of the other observations you've made and with the requirements of a metric (e.g., with the triangle inequality), so all three are possible; but they require different outputs. Thus, if your algorithm doesn't examine that edge and then outputs something, an adversary can always choose a length for the unexamined edge that will make your algorithm's output wrong.
However, if you know that all the points live in $\mathbb{R}^d$ (even though you are not given their coordinates), then the problem can be solved by measuring $O((d+1)n)$ distances, assuming no degeneracies (no subset of $d+1$ points are co-planar).
In particular, pick $d+1$ points randomly. These will be anchor points. Given their pairwise distances, you can compute coordinates for them that are consistent with their pairwise distances. Now, for every other point $P$, compute the distance from $P$ to each of the anchor points. Using triangulation and these distances, you can compute the location of $P$ relative to the anchor points and thus the coordinates for $P$. Do this for every non-anchor point $P$. Now you have coordinates for every point, and you can use those coordinates to find the central point without asking the oracle to give you any more pairwise distances. I don't know whether this last step can be done faster than $O(n^2)$ time, but it can be done without measuring any more pairwise distances.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45122
0 comments:
Post a Comment
Let us know your responses and feedback