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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - Average distance minimization | Date |
---|---|

MATLAB and averaging without NaN | Jun 10, 2017 |

C/++/# Can someone code review my "Distance between nodes in a BT"? | Feb 3, 2017 |

Fortran Problems when averaging a value | Sep 28, 2016 |

A problem when calculating the average of an array (c programming )? | May 1, 2013 |

Several ascii files, read, write, average? | Jun 9, 2011 |

**Physics Forums - The Fusion of Science and Community**