Talk:Space-filling curve

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:
This article has an assessment summary page.

Contents

[edit] A curve filling a countably dimensional hypercube

You should describe such a curve. Also, you should make a link to a description of the discontinuous mapping of the unit interval onto the unit square, discovered by Georg Cantor. -- Leocat 14:13, 25 October 2006 (UTC)

[edit] Space-filling curves are not bijections

So this space-filling curve is a continuous bijection, right? Why isn't it a homemomorphism (it certainly can't be). Because its inverse isn't continuous? That must be it. Lethe | Talk 07:42, Mar 3, 2005 (UTC)

Space filling curves aren't one to one, so aren't bijections.(Balthamos 23:35, 11 June 2006 (UTC))

[edit] Any space-filling curve must be densely self-intersecting

Wasn't one of the attributes of the Peano curve the property of non self-intersection? WLD 13:14, 23 Apr 2005 (UTC)

There cannot be any non-self-intersecting (i.e. injective) continuous curve filling up the unit square, because that will make the curve a homeomorphism from the unit interval onto the unit square (using the fact that any continuous bijection from a compact space onto a Hausdorff space is a homeomorphism), but the unit-square (which has no cut-point) is not homeomorphic to the unit interval (all points of which, except the endpoints, are cut-points).
A.D.
The problem may be unfamiliarity with the definition of "self-intersecting". Here it just means that curve is not simple (not injective). Two curves intersect if the intersection of their images is non-empty, and if a curve is not simple we can find two "subcurves" of the curve (obtained by taking the restrictions to two disjoint segments of its domain) that intersect. But, in analogy to the intersection of lines, one might be tempted to think (incorrectly) that the meaning of "curves intersecting" is that they cross each other, going to the other side. And for the Peano curve (and also the Hilbert curve), whereever two subcurves intersect, they don't cross.  --Lambiam 02:52, 11 November 2007 (UTC)

[edit] Self-avoiding property of finite approximations

Under the Properties heading, the article says

  • Peano's original construction is self-contacting at all finite approximations, but Hilbert's construction is self-avoiding for all finite approximations.

But this is not true: First, Peano's original construction does not even use finite approximations. Instead, it is defined directly in terms of the trinary digits of the argument (!). Second, his construction could be described in terms of self-avoiding finite approximations, as the figure in the article clearly shows. And third, properties of finite approximations are not properties of the curve, so they don't belong under the Properties heading anyway. Accordingly, I am going to delete the statement. Hanche 16:37, 2 September 2007 (UTC)

[edit] Proof that a square and its side contain the same number of points

The formal proof kindly provided by JRSpriggs (around which I built this section) involves the definition of a right-inverse which seems not to be a ("proper") function, because it yields nonunique results... This is because the original space-filling curve is self-intersecting. Was I clear enough? Am I right? Is this right inverse compatible with Cantor–Bernstein–Schroeder theorem? Paolo.dL 15:19, 7 September 2007 (UTC)

Using the axiom of choice, we can get a right inverse to any surjective function. In fact, asserting the existence of an inverse to every surjective function is AC. I sense there might be away to get around AC by using directly some sort of dual to C-B-S, but I doubt there's actually a constructive proof. Depends what you call "proper" I guess. --192.75.48.150 17:40, 7 September 2007 (UTC)
This relation is not a proper function (one input has two outputs). It is sometimes called a multivalued function.
This relation is not a proper function (one input has two outputs). It is sometimes called a multivalued function.

OK, here is the figure with the explanation of the word "proper" or "true" (from the article Function). Paolo.dL 18:26, 7 September 2007 (UTC)

Right. In your picture, let's say f(a) = 1, f(d) = 2, f(b) = f(c) = 3. f is a surjection from Y to X. You can use either
g(1) = a, g(2) = d, g(3) = b or
h(1) = a, h(2) = d, h(3) = c
as a right inverse - they are both injections from X to Y. But of course you also see there's no injection from Y to X. For the infinite case, to actually define the right inverse and make the proof work, you need to assume the axiom of choice (see that article for more details). --192.75.48.150 19:03, 7 September 2007 (UTC)

Yes! In other words, a space-filling curve, being self-intersecting, is similar to the function f: Y \to X obtained by just reversing the arrows in the figure. This suggests that, paradoxically, there could be even "more points" in the side of the square (Y) than in the square (X)! By the way, that's plausible somehow: the tangent function proves that a finite-length segment can contain the same number of points as an infinitely long line... [of course I know that the two infinite sets have the same cardinality \mathbf c, but I am trying to describe the concept in a more intuitive way].

And you are right: contrary to what I wrote, the two right inverses of f (g and h) are by all means true (proper) functions. I was confusing the right inverse of f with the multivalued function shown in the figure on the right, which would be a "quasi-inverse" of f, rather than one of its right inverses.

Thanks a lot. It was very kind of you to explain. What's more important is that the proof in the article is correct. This is nice because the proof can be intuitively interpreted as I wrote above and in the article (even by those who do not totally understand it). It provides good food for thought. :-) Paolo.dL 20:55, 7 September 2007 (UTC)

Thanks also to JRSpriggs for his latest enlightening contribution to this section. In this context, it is amazing that Hilbert was able to associate up to four points in the side to each point in the square! (see also the discussion Intuitively acceptable examples about "larger than infinite", from which the idea of creating this section originated) Paolo.dL 09:33, 9 September 2007 (UTC)

[edit] Bad illustration

The first illustration on this page has the caption: "3 iterations of the Peano curve, a space-filling curve" But the illustration is actually just another picture of the Hilbert curve. The Hilbert curve is a Peano curve, but as far as I can gather it is not the curve the Peano came up with. So either the illustration should be replaced with an illustration like this: http://mathworld.wolfram.com/PeanoCurve.html Which I believe is 'The Peano Curve' Or we should change the illustration caption to say 'a Peano curve' instead of 'The Peano curve', but if we're going to just change the caption the illustration should probably just be removed, 'cause it is redundant with a hilbert curve illustration directly below it. 128.97.68.15 21:35, 10 October 2007 (UTC)

Let us use "Peano curve" for the actual curve invented by Peano. Then the Hilbert curve and the Peano curve are different things. The Peano curve consists of 3×3 reduced copies of itself glued together, while the Hilbert curve is the union of 2×2 reduced copies of itself. (Here, reduced = reduced in scale). The first image does indeed show the construction of the actual first Peano curve, and shows a different curve than the next image, the Hilbert curve.  --Lambiam 22:42, 10 October 2007 (UTC)
I must agree with Lambiam on this. If you check out Peano's paper from 1890 (referenced in the article), you will not see a picture, but a description of the parametrization of the curve based on the base 3 representation of the parameter. It takes a bit of work to puzzle it out, but the picture in the article as it is now is correct. Hanche 17:10, 12 October 2007 (UTC)

[edit] Relationship of Space-filling to Tiling and tessellation

Comparing the Sierpinski Triangle and Carpet to tiling arrangements, it would appear that the technique is applicable to repetitive tiling arrangement; triangle, square, hexagon being the simplest. It would seem impossible to apply it to other than rep-tile arrangements. —Preceding unsigned comment added by 86.160.138.236 (talk) 12:05, 2 June 2008 (UTC)

I think you are right (except that "impossible" is, in general, too strong). However, the Wikipedia verifiability policy requires that we only put content in our articles that has been published before in reliable sources. Even if true, content based on original research must not be added. Therefore I have removed this addition from the article.  --Lambiam 18:00, 2 June 2008 (UTC)