Jump to content

Talk:Tight span

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Who Discovered It?

[edit]

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

Notation

[edit]

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

Finite?

[edit]

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)[reply]

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)[reply]
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)[reply]
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)[reply]

Manhattan Plane

[edit]

R2 is injective with the L1 metric but R3 is not. Vegasprof 10:04, 10 November 2006 (UTC)[reply]

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)[reply]

Applications to Online Algorithms

[edit]

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)[reply]

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)[reply]
You're right. Vegasprof 21:50, 11 November 2006 (UTC)[reply]
I fixed the ambiguity of the statement. Oravec 22:09, 11 November 2006 (UTC)[reply]


Great Contribution

[edit]

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

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

References

[edit]

Isn't

  • Holsztyński, Włodzimierz (1968). "Linearisation od isometric embeddings of Banach Spaces. Metric Envelopes.". Bull. Acad. Polon. Sci. 16: 189-193.

supposed to be

I imagine so. Done. —David Eppstein (talk) 05:26, 2 March 2008 (UTC)[reply]

Tropical approach

[edit]

In the article it says

Develin & Sturmfels (2004) provide an alternative definition of the tight span of a finite metric space, as the tropical convex hull of the vectors of distances from each point to each other point in the space.

but the Erratum to their paper seems to retract the theorem that the tropical convex hull is the tight span. SimonWillerton (talk) 22:58, 30 November 2012 (UTC)[reply]

Indeed it does! It says specifically that:

If D is a symmetric matrix which represents a finite metric, then the tropical polytope PD always contains Isbell’s injective hull of the metric, but in general these two polyhedral spaces are not equal.

That is, the tropical convex hull always contains the tight span, but may be larger. I've amended the article to show this mis-step and its correction, citing the Erratum article. Rather than expunging the error, it's reasonable to show that doing mathematics (or any other science) is an ongoing process, subject to correction when we err. yoyo (talk) 13:13, 30 March 2017 (UTC)[reply]