Re: minimize avg distance to some points
- To: mathgroup at smc.vnet.net
- Subject: [mg38314] Re: [mg38244] minimize avg distance to some points
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Thu, 12 Dec 2002 01:32:57 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
On Tue, 10 Dec 2002, Daniel Reeves wrote:
> Interesting optimization problem:
> Given a list of n-dimensional points, find a point that minimizes the
> average distance to all the given points.
>
> For example, here are 4 points in 3-space:
>
> points = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};
>
> Here's the formula for euclidean distance:
>
> d[p1_, p2_] := Sqrt[Tr[(p1 - p2)^2]]
>
> Now we want to find the point where all the partial derivatives are 0:
>
> eq[i_] := D[Tr[d[Array[z, 3], #] & /@ points], z[i]]
>
> eqs = (eq[#] == 0 & /@ Range[3])
>
> Solve[eqs, {z[1], z[2], z[3]}]
>
> But Mathematica chokes on that...
>
> Any ideas for a better algorithm to find the total-distance minimizing
> point (this should work for any dimensions; 16 in my case)?
>
> Thanks!
> Daniel
>
> --
> Daniel Reeves -- http://ai.eecs.umich.edu/people/dreeves/
>
> Humans are genes' way of making more genes. -- Richard Dawkins
search terms: "Euclidean 1-median problem" "Fermat-Weber problem"
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/