Talk:Tight span

From Wikipedia, the free encyclopedia

Contents 1 Who Discovered It? 2 Notation 3 Finite? 4 Manhattan Plane 5 Applications to Online Algorithms 6 Great Contribution

[edit] Who Discovered It?

John Isbell, in 1964. Vegasprof 09:58, 8 November 2006 (UTC)

[edit] Notation

I believe that in the T-theory literature, the tight span of X is normally called T(X) or T_X. Vegasprof 20:27, 8 November 2006 (UTC)

[edit] Finite?

The tight span is defined for all metric spaces, not just finite metric spaces, although the applications that I have seen all seem to be for finite metric spaces. Vegasprof 19:05, 9 November 2006 (UTC)

Right, that's why I moved the part about finiteness into the formal definitions section, and left the introductory sections talking about metric spaces more generally. I am not certain whether the definition here is correct for infinite spaces, whether perhaps the condition on existence of y s.t. f(x)+f(y)=d(x,y) should be replaced by inf f(x)+f(y)-d(x,y)=0, or whether something else is required in the infinite case, so I thought it best to stick to material I was more certain I understood. —David Eppstein 19:33, 9 November 2006 (UTC)

Later: I found the right definition in Dress et al (it is the inf version) and added it as a footnote. —David Eppstein 22:43, 9 November 2006 (UTC)

I see. For example, the tight span of the rationals is the reals, and you really need to say "inf." Vegasprof 10:04, 10 November 2006 (UTC)

[edit] Manhattan Plane

R² is injective with the L₁ metric but R³ is not. Vegasprof 10:04, 10 November 2006 (UTC)

Yes, that's one of the reasons the connection to orthogonal hull is hard to generalize to higher dimensions. I suppose I should say more about how two-dimensional L1 and Linf are related somewhere in that example. —David Eppstein 16:07, 10 November 2006 (UTC)

[edit] Applications to Online Algorithms

Besides the k-server problem, what other published applications to online algorithms do you know of? I didn't find any when I was looking. Vegasprof 10:04, 10 November 2006 (UTC)

I don't know of any, but I think that line is left over from Oravec's earlier version, so you could try asking him...—David Eppstein 16:07, 10 November 2006 (UTC)

You're right. Vegasprof 21:50, 11 November 2006 (UTC)

I fixed the ambiguity of the statement. Oravec 22:09, 11 November 2006 (UTC)

[edit] Great Contribution

Wow, you guys developed this article nicely in a short period of time. Congrats. Tparameter 20:10, 10 November 2006 (UTC)

Thanks mostly to David. Vegasprof 21:50, 11 November 2006 (UTC)