This could be a well-known problem, but I looked around and I don't see anything.(adsbygoogle = window.adsbygoogle || []).push({});

Suppose there is a set of points [tex]p_1, p_2, ... p_N[/tex]. For simplicity, assume Euclidean space of arbitrary dimensionality, but this could be any metric space.

I need to find a new set [tex]q_1, q_2, ... q_n[/tex] of n points, where n is less than N, that "approximates" the original set by minimizing the average distance between points in the original set & the new set.

In other words, I need to minimize

[tex]\sum_1^{i=N} \min_1^{j=n} |p_i-q_j|[/tex]

There's an obvious brute-force solution, but complexity [tex]n^N[/tex] makes it completely useless for large N, which could be 1000 or more. I can cook up an iterative algorithm that gives me a local minimum in a reasonable amount of time, but I have no confidence that the local minimum will be anywhere near the global minimum.

Can this problem be solved exactly in polynomial time?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Average distance minimization algorithm

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**