--- Dave Mitchell <[EMAIL PROTECTED]> wrote: > On Thu, Jul 11, 2002 at 01:18:51PM -0700, John Porter wrote: > > Nicholas Clark wrote: > > > I was thinking that the metric (x*x + y*y) would be fast to > > > calculate, as that's all we need for ordering. > > > > Point is, it's rather *more* than we need for ordering. > > x + y will suffice. > > IIRC, all metrics of the form (x^n + y^n)^(1/n), n=1,2,...Inf > are strongly equivalent, ie they give rise to the *same* ordering. > (In the limit as n -> Inf, the metric is max(x,y).)
This has already been corrected, but as a lurking mathematician I should perhaps explain. The metrics (or "L_p norms", as We In The Know call them) (|x|^p + |y|^p)^(1/p) (p>=1 any real number) do *not* give equivalent orderings on distances. E.g. for the taxicab metric (p=1), if you pay for 50km, you can go 30km east and 20 km north; but if you pay Euclid (p=2) to drive you there, you can go 30km east and 40km north. Thus, the point (30,40) is closer to the origin than the point (60,0) when p=2, but further away when p=1. What *is* equivalent is the topology. If a sequence converges with respect to *any* norm (and these distances are all norms), then it converges with respect to *all* norms. (This is true for any finite number of dimensions when working with real numbers.) In other words, the realm of the very small looks roughly similar no matter which p you choose. We're talking about integer x,y, and in particular they're not very small. So topology is probably not relevant; the choice of norms makes a difference. __________________________________________________ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
