       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[]]==0 )

diameter[hd_]:={hd[[1,1]],Last[hd[]],Sqrt[N[hd[
[1,2]]]]}/;(
Length[hd[]]==0)

diameter[hd_]:=Module[{dd,nx},
dd=SetToPointDistance[hd[[2,1]],hd[]];
nx=Max[dd];
If[nx		< hd[[1,2]],
diameter[{hd[],Drop[hd[],1],hd[]}],
diameter[{{hd[[2,1]],nx},Drop[hd[],1],
Drop[hd[],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] ====

```

• Prev by Date: Re: Matching random numbers
• Next by Date: Postfix (//) with Options? (SUMMARY)
• Previous by thread: Re: The farthest apart points problem
• Next by thread: Re: The farthest apart points problem