Re: The farthest apart points problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg4620] Re: The farthest apart points problem*From*: Riccardo Rigon <rigon at csrp.tamu.edu>*Date*: Wed, 21 Aug 1996 03:25:36 -0400*Organization*: EOWR TAMU*Sender*: owner-wri-mathgroup at wolfram.com

Based on the suggestions I had from the news group, I did this mathematica program calculating the two farthest apart points in a set of vertex of a convex hull. Unfortunately I could not find in my libraries the Shamos and Preparata textbook suggested by David Eppstein who I thanks anyway. Other contributions come from D aniel Lichtbau, Bruce Alan and a forth guy whose name unfortunaly I have lost. This is my solution SetToPointDistance[pt_,set_]:=(Plus @@ ((#-pt)^2))& /@set diameter[hd_]:={hd[[1,1]],hd[[3,1]],Sqrt[N[hd[[1,2 ]]]]}/; (Length[hd[[2]]]==0 ) diameter[hd_]:={hd[[1,1]],Last[hd[[2]]],Sqrt[N[hd[ [1,2]]]]}/;( Length[hd[[3]]]==0) diameter[hd_]:=Module[{dd,nx}, dd=SetToPointDistance[hd[[2,1]],hd[[3]]]; nx=Max[dd]; If[nx < hd[[1,2]], diameter[{hd[[1]],Drop[hd[[2]],1],hd[[3]]}], diameter[{{hd[[2,1]],nx},Drop[hd[[2]],1], Drop[hd[[3]],Position[dd,nx][[1,1]]-1]}] ] ] Diameter[data_]:=Module[{pt=First[data], st=Rest[data]}, dis=SetToPointDistance[pt,st]; mx=Max[dis]; diameter[{{First[data],N[mx]},Take[st,#],Drop[st,# -1]}]& @ ( Position[dis,mx][[1,1]]) ] ON2[data_]:=Max[Sqrt[N[SetToPointDistance[#,data]& /@data]]] ON2 is the trivial O(N^2) solution Diameter[data] where "data" contains the vertex of the convex hull works a little bit faster (ordered). The function "diameter" is based on the fact that given a vertex and the most distant other vertex from it, the farthest apart points is either: 1) the pair one already has (say A and B); 2) a pair which one point stay from one side of the line AB and the other on the other side. 3) a pair of ehich one point is point B and the second is on one of the two sides Any better/more elegant/faster solution ? Riccardo Rigon ==== [MESSAGE SEPARATOR] ====