On Fri, Jan 20, 2006 at 05:29:46PM -0500, Ron wrote:
> If the N-dimensional space is Euclidean (any <x, x+1> is the same
> distance apart in dimension x), then finding the farthest pair can be
> done in at least O(n).
That sounds a bit optimistic.
http://portal.acm.org/ft_gateway.cfm?id=167217&type=pdf&coll=GUIDE&dl=GUIDE&CFID=66230761&CFTOKEN=72453878
is from 1993, but still it struggles with getting it down to O(n log n)
deterministically, for Euclidian 3-space, and our problem is not Euclidian
(although it still satisfies the triangle inequality, which sounds important
to me) and in a significantly higher dimension...
/* Steinar */
--
Homepage: http://www.sesse.net/