Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Average distance minimization algorithm

  1. Nov 1, 2009 #1
    This could be a well-known problem, but I looked around and I don't see anything.

    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted