Re: Point on sphere greatest distance from given

*To*: mathgroup at smc.vnet.net*Subject*: [mg104091] Re: Point on sphere greatest distance from given*From*: Ray Koopman <koopman at sfu.ca>*Date*: Mon, 19 Oct 2009 07:10:15 -0400 (EDT)

On 18 Oct 2009, at 3:54 am, Andrzej Kozlowski wrote: > On 18 Oct 2009, at 18:23, Ray Koopman wrote: >> On Oct 17, 3:58 am, Kelly Jones <kelly.terry.jones at gmail.com> wrote: >>> How can I use Mathematica to solve this problem: >>> >>> Given n points on a sphere, I want to find a point x such that: >>> >>> Sum[distance[x,i],{i,1,n}] >>> >>> is maximal, where "distance" is spherical ("great circle") distance. >>> >>> In other words, I want to find the point x "furthest" from the >>> given n points. >>> >>> Is there any chance x will coincide with one of the given points? >>> If so, is there a better notion of distance to use? >> >> To avoid having the solution coincide with one of the >> given points, maximize the sum of the logs of the distances. >> >> s = Normalize/@RandomReal[NormalDistribution[0,1],{5,3}] >> >> {{-0.528071, -0.848197, 0.0412642}, >> {-0.0563032, -0.978864, -0.196608}, >> {0.750442, 0.305033, 0.586337}, >> {0.384831, 0.263578, 0.884552}, >> {0.922298, 0.0757753, 0.378977}} >> >> NMaximize[{Tr at Log[1-s.Normalize@{x,y,z}],x^2+y^2+z^2==1},{x,y,z}] >> >> {2.00971, {x -> -0.497972, y -> 0.585326, z -> -0.639858}} >> >> Although the final {x,y,z} is always normalized, the >> trial values are not, so we must normalize them manually. > > Maybe I am missing something, but this seems wrong to me. The "great > circle" distance between two points on the unit sphere is simply the > solid angle between their respective postition vectors. Now, s.{x,y,z} > gives the cosines of the angles between the position vectors of the > points of the set s and the point {x,y,z} so I think what you should > be maximizing the sum of Abs[ArcCos[s.{x,y,z}]]. So with the same data > as above I would compute: > > NMaximize[{Tr at Abs[ArcCos[s.{x, y, z}]], > x^2 + y^2 + z^2 == 1}, {x, y, z}] > > {10.8542, {x -> -0.750877, y -> 0.0409026, z -> -0.659196}} > > (which is not one of the points of the set s) > > while your approach gives: > > NMaximize[{Tr@Log[Abs[1 - s.{x, y, z}]], > x^2 + y^2 + z^2 == 1}, {x, y, z}] > > {2.00971, {x -> -0.497972, y -> 0.585326, z -> -0.639858}} > > ? > > Andrzej Kozlowski You're right. I was using linear distance (thru the interior of the sphere), not circular distance (on the surface of the sphere). When I went to logs, I forgot that I was using the wrong distance. This maximizes the sum of the logs of the circular distances: NMaximize[{Tr@Log@ArcCos[s.Normalize@{x,y,z}],x^2+y^2+z^2==1},{x,y,z}] {3.72509, {x -> -0.596069, y -> 0.437286, z -> -0.673411}} The reason I was working with linear distance is that the squared linear distance = 2(1-cos), and cos is approximately linear over [0,Pi], so maximizing the sum of the circular distances should be approximately equivalent to maximizing the sum of squared linear distances, which in turn is exactly equivalent to minimizing the sum of the cosines, which has a closed-form solution: -Normalize@Total[s]. For the s in my example that gives {-0.580501, 0.466023, -0.667713}.