9
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Without the triangle inequality (or some other way of gaining information about unmeasured edges), $O(n^2)$ is the only solution; this can be seen by an antagonist argument. $\endgroup$
    – Kittsil
    Aug 9, 2015 at 14:55
  • $\begingroup$ Assume the triangle inequality is available - it should be for my metric. $\endgroup$
    – Open Door Logistics
    Aug 9, 2015 at 15:14
  • $\begingroup$ This is essentially computing the radios of a graph with triangle equality. $\endgroup$
    – Kaveh
    Aug 9, 2015 at 15:26
  • $\begingroup$ @Kaveh I guess you mean the radius ... unless the graph has a broken edge. I am making sure as there is too much vocabulary I do not know. --- But it is then a complete graph, and the input size is only the number of vertices. $\endgroup$
    – babou
    Aug 9, 2015 at 16:46
  • $\begingroup$ @OpenDoorLogistics If it doesn't have the triangle inequality, it's not a metric space, by deifinition. Please clarify the question: if you know it's a metric space, then you know it has the triangle inequality; if you don't know it has the triangle inequality, you can't claim it's a metric space. $\endgroup$
    – David Richerby
    Aug 9, 2015 at 17:26

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You have $n$ points in dimension $n-1$. Even looking at all the coordinates of the input requires $\Theta(n^2)$ time. $\endgroup$
    – Louis
    Aug 10, 2015 at 7:54
  • $\begingroup$ @Louis The question says nothing about dimensions, and is not sure it is a metric. All we have is the triangle inequality. So the proper view is that of Kaveh's comment: as a complete graph. That is consistent with this answer. But I have no idea whether it is consistent with any fixed metric when $n$ grows without bound. $\endgroup$
    – babou
    Aug 10, 2015 at 8:53
  • $\begingroup$ @D.W. Thanks - could we do anything better in the average case though? This is motivated by a real-world problem, so the data is likely to be 'average' (whatever that might mean). $\endgroup$
    – Open Door Logistics
    Aug 10, 2015 at 9:07
  • $\begingroup$ @all - apologies for the confusion re: metric (I am a laymen in theoretical CS). My distance function definitely obeys the 4 criteria for a metric space, as per the Wikipedia definition of a metric space link. $\endgroup$
    – Open Door Logistics
    Aug 10, 2015 at 9:10
  • $\begingroup$ @OpenDoorLogistics, I have added one special case where it seems possible to do better. $\endgroup$
    – D.W. ♦
    Aug 10, 2015 at 16:15
0
$\begingroup$

Check out Piotr Indyk's work on fast algorithms for metric spaces. (Sublinear Algorithms for Metric Space Problems, in Proceedings of STOC '99, pp.428–434. ACM, 1999; PS) Section 3 gives a linear-time approximate 1-median algorithm.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Could you give a summary of the algorithm? We're ideally looking for full answers, rather than links to external content. $\endgroup$
    – David Richerby
    May 7, 2017 at 8:59
  • $\begingroup$ Apologies for the very slow reply. I obviously don't check StackExchange very often. I think that it would take me more than an hour to write a halfway decent summary, whereas Piotr's paper is beautifully written, explains the algorithm very crisply, and has all the precise definitions next to it. So I would personally strongly recommend making use of this high-quality external content, rather than the medium-quality internal content I could produce. The short answer is: If you are willing to just find an approximate median, you can do so in linear time O(n). $\endgroup$
    – user71641
    Oct 21, 2017 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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