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/
