From: Fred Galvin Subject: Re: Peano space filling curve Date: Tue, 15 Aug 2000 18:24:21 -0500 Newsgroups: sci.math Summary: [missing] On Tue, 15 Aug 2000, it was written: > > Apparently the peano space filling curve is continuous when viewed as a > > function from [0,1] to [0,1]x[0,1] and bijective, does anyone know what > the > > form of the function is, and how to prove that it is continuous and > > bijective? Thanks, > > OK, it's not bijective, it's surjective, can anyone tell me how to prove > that it is surjective? > > Also, I'd like to know a way of parameterising the curve because I can't > think of a good way of doing so without having some problem points (I had a > go, but there was a problem at the endpoints). Here's one way to construct a Peano curve. Define continuous functions fn:[0,1] --> [0,1] for n = 1,2,3,... as follows. Define f1 so that f1(t) = 0 for t in [0, 1/3], f1(t) = 1 for t in [2/3, 1], and (say) f1(t) = 3t-1 for t in [2/3, 1]. Define f2 so that f2(t) = 0 for t in [0, 1/9], f2(t) = 1 for x in [2/9, 1/3], f2(t) = 0 for t in [2/3, 7/9], f2(t) = 1 for t in [8/9, 1]. And so on. Note that, given any infinite sequence b1, b2, ... of 0s and 1s, you can find a point t in [0,1] (in fact, in the Cantor set) such that fn(t) = bn for all n. Now define g:[0,1] --> [0,1] and h:[0,1] --> [0,1] as follows: g(t) = f1(t)/2 + f3(t)/4 + f5(t)/8 + f7(t)/16 + ..., h(t) = f2(t)/2 + f4(t)/4 + f6(t)/8 + f8(t)/16 + ..... The functions g and h are continuous, because their defining series are uniformly convergent series of continuous functions. So the curve x = g(t), y = h(t) is a continuous curve in the unit square. Now consider any point (x,y) in [0, 1]x[0, 1]. Find binary expansions x = (a1)/2 + (a2)/4 + (a3)/8 + ..., y = (b1)/2 + (b2)/4 + (b3)/8 + .... As noted previously, we can find t in [0, 1] such that f1(t) = a1, f2(t) = b1, f3(t) = a2, f4(t) = b2, f5(t) = a3, and so on. Thus the function t |--> (g(t), h(t)) maps the interval [0, 1] continuously onto the square [0, 1]x[0, 1]. It should be clear how to modify the construction to get a continuous curve filling up the 3-dimensional or aleph_0 dimensional cube. -- "Any clod can have the facts, but having opinions is an art."--McCabe ============================================================================== From: Fred Galvin Subject: Re: Peano space filling curve Date: Thu, 17 Aug 2000 20:36:24 -0500 Newsgroups: sci.math On Fri, 18 Aug 2000, it was written: > > Here's one way to construct a Peano curve. > ... > > As noted previously, we can find t in [0, 1] such that f1(t) = a1, > > f2(t) = b1, f3(t) = a2, f4(t) = b2, f5(t) = a3, and so on. Thus the > > function t |--> (g(t), h(t)) maps the interval [0, 1] continuously > > onto the square [0, 1]x[0, 1]. > > > > It should be clear how to modify the construction to get a continuous > > curve filling up the 3-dimensional or aleph_0 dimensional cube. > > Ah, that's very clever, I like it! This isn't the same curve that > Peano came up with though, is it? Thanks a great deal for this > construction. I'm glad you like it! I'm sorry, but I'm not in a position to answer your historical question, as I've never looked at Peano's original construction. My *guess* is that the constructions must be pretty much the same in principle, though the formal details may differ somewhat. You could try graphing an approximation to the curve I defined, by truncating the infinite series after 2 or 3 terms, and see how it compares with the approximate Peano curves depicted in books. Hmm. I've seen another construction, which maps the unit inverval onto a solid *triangle* (instead of a square); maybe *that* was Peano's construction, but I wouldn't know. Here is a terse description: You start with a right triangle, divided into two smaller right triangles by dropping an altitude from the right angle; then each of the small triangles is divided into two even smaller triangles in the same way, and so ad infinitum. Now, use the binary expansion of a real number t in [0,1] to determine a nested sequence of triangles, which converges to a point f(t). You have to show that f is well-defined at values of t with nonunique binary expansion, and that f is continuous and that its range fills up the whole triangle. -- "Any clod can have the facts, but having opinions is an art."--McCabe ============================================================================== From: ullrich@math.okstate.edu (David C. Ullrich) Subject: Re: Peano space filling curve Date: Wed, 16 Aug 2000 15:24:38 GMT Newsgroups: sci.math On Tue, 15 Aug 2000 16:59:58 +0100, "Dan Goodman" wrote: >> Apparently the peano space filling curve is continuous when viewed as a >> function from [0,1] to [0,1]x[0,1] and bijective, does anyone know what >the >> form of the function is, and how to prove that it is continuous and >> bijective? Thanks, > >OK, it's not bijective, it's surjective, can anyone tell me how to prove >that it is surjective? Ok, seriously: >Also, I'd like to know a way of parameterising the curve This is not an "also", the curve _is_ its parametrization! Seriously: A curve in R^2 is by definition a continuous function mapping an interval to R^2, _not_ a subset of R^2. If a curve were a subset of R^2 then that black square you wondered about _would_ be a complete description of the curve. > because I can't >think of a good way of doing so without having some problem points (I had a >go, but there was a problem at the endpoints). Here's a way to think about it geometrically: It's going to be the limit of a sequence of polygonal curves. Say the square is S. Divide S into four subsquares and call them S00, S01, S10, S11, in what I hope is obvious notation. The first curve is just going to be a polygon connecting the centers of those four subsquares. In this order: S00, S01, S11, S10. Each step is supposed to be up, down, left or right - jumping from S00 to S11 along the diagonal is not allowed. For the second curve: Divide S into 16 subsquares each of side length 1/4. The second curve is going to connect the centers of those 16 squares, in the right order. There are two rules: (i) Each jump is from a square to an adjacent square (ii) The ordering of the 16 square of length 1/4 is "compatible" with the ordering we chose previously for the four sqaures of side 1/2. That is, first we run through the four quarters of S00, then the four quarters of S01, then the quarters of S11 and finally the quarters of S10. It's not obvious at first that you can accomplish both (i) and (ii) simultaneously but you can. Say the quarters of S00 are S0000, S0001, S0010, and S0011. If we go through them in the order S0000, S0001, S0011, S0010 we're in trouble, because the final square S0010 is not adjacent to any of the quarters of S01. But we can run through them in this order: S0000, S0010, S0011, S0001. Now S0001 _is_ adjacent to one of the quarters of S01; it's adjacent to S0100, in fact. So now when we run through the four quarters of S01 we're required to start with S0100, and we're required to end at a square adlacent to one of the quarters of S11. We can do that. Then we start at that quarter of S11 and run through the four quarters of S11 in such a way as to end at a square adjacent to one of the quarters of S10... And so on. The n-th curve is a polygon connecting the centers of the 4^n subsquares of S of side length 2^(-n), in such a way that each jump is to an adjacent subsquare. The (n+1)-th curve is a "refinement" of the n-th, in the sense that its ordering of the 4^(n+1) subsqaures of side 2^(-n-1) "respects" the ordering of the next-larger squares defined by the previous curve. It's not immediately obvious that this is possible, but you draw a few pictures - At the "next" stage you have to decide how to order the 4 subsquares of one of the "previous" squares, you're forced to start at one of them and required to end at one adjacent to the next one of the "previous" squares. You draw a few pictures, you see there are only three really different things that can happen, and you verify that you can find an ordering of those 4 squares in each case that meets the requirements. Now those curves approach something as n -> infinity. That something is a curve, and it intersects every one of the subsquares of S at every level - so it must in fact pass through every point of S. >Also, I'm quite interested in how you make the idea of the limit of a set of >piecewise linear curves rigorous (e.g. the Koch curve of Peano curve). How >do you tell (in general) when there is such a limit (obviously there won't >always be a limit), The reason there is a limit here, and that the limit is continuous, is that you can parametrize the n-th curve to get uniform convergence. This is the point to the "compatibility" at various levels: Since the squares at the next level are traversed in an order that gives a refinement of the order in which the squares at the previous level were traversed you see that in fact (*) |C_(n+1)(t) - C_n(t)| <= c*2^(-n), if C_n(t) is the parametrization of the n-th curve. And the sum of 2^(-n) is finite - so the C_n converge uniformly to something continuous. ********************* If you take various more obvious approaches that don't work the reason they don't is there's nothing analogous to (*) available. For example, you could draw 2^n evenly spaced vertical lines in S, each extending from the bottom to the top, and then define a curve by traversing these vertical lines in an up/down sort of way (running along the top or bottom of S to get from one line to the next). This gives you a family C_n of curves that looks like it sort of fills out the square. But there's no way to parametrize these curves so that the corresponding functions have a limit - in fact no matter how you parametrize them it will be true that for all n there exists t with |C_(n+1)(t) - C_n(t)| > 1/2 or 1/4 or something, about as far from (*) as you can get. ****************** A fairly nonsensical but perhaps intuitively appealing way to look at essentially the same thing: We show by induction on L > 0 that if S is a square of side length L and p, q are two adjacent coners of S then there exsts a continuous function C: [0,1] -> S such that C([0,1]) = S, C(0) = p and C(1) = q. For the induction step we assume that we can do this for square of side length L/2. If we can do this for squares of side length L/2 we can take four of those smaller space-filling curves and piece them together to get a curve filling our square of side length L. (Fill S00, starting at (0,0) and ending at (0,1/2). Now fill S01, starting at (0,1/2) and ending at (1/2,1/2). Then fill S11, starting at (1/2,1/2) and ending at (1,1/2), and finally fill S10, starting at (1,1/2) and ending at (1,0). Each starting point is the endpoint of the previous quarter curve so we get something continuous when we fit them together.) That's nonsense because there's no such thing as induction on the positive reals. (The alert reader may have noticed that squares of side L/2 are really not much easier than squares of side L...) But if epsilon > 0 and we pretend we cannot distinguish points that are within epsilon of each other then for larger enough n a square of side L/2^n is just a single point - we _can_ construct a single-point-filling curve, and that _does_ give a "space-filling- within-epsilon" curve. So this does give a way to construct space-filling "curves" if points in space have a finite resolution. In particular this does give a way to generate that gif... Or you could say it gives an alternate way to show that those "refinements" are possible in the previous version. > and what the limit is? Similarly, is there a decision >procedure to determine whether or not a point is on the curve? In general I don't think so. (Although exactly what this even means is not as clear as you might think - real numbers are not the sort of things you can describe in finite terms suitable for plugging into a "procedure".) But for example I don't think there's a procedure for deciding whether a given construction analogous to the above, or equivalently, defined by some infinite series, actually defines a space-filling curve. >Thanks, >Dan Goodman > ============================================================================== From: ullrich@math.okstate.edu (David C. Ullrich) Subject: Re: Peano space filling curve Date: Fri, 18 Aug 2000 14:06:18 GMT Newsgroups: sci.math On Fri, 18 Aug 2000 02:10:34 +0100, "Dan Goodman" wrote: >> Now those curves approach >> something as n -> infinity. That >> something is a curve, and it intersects >> every one of the subsquares of S at >> every level - so it must in fact pass >> through every point of S. > >OK, I follow the construction so far, but I don't follow this last step. I >can see that it will intersect each square at every level, Say the function from [0,1] to S we just constructed is gamma. The "image" gamma([0,1]) is a compact set, hence it is a closed subset of S. If it intersects every one of those dyadic squares it's also a dense subset of S. So it's S. Not knowing who you are I'm not sure whether that's the best answer. Can be easily rephrased without the fancy words. (Or see below) > but every point >on the side of each of these squares has at least one coordinate (x or y) >that is 2^-n for some n, so would a point like, for instance >(1/sqrt(2),1/sqrt(2)) be mapped onto? Yes. Another way to look at it: Say p is a point of the square. Then p is an element of one of those quarter squares S00, S01, S10, S11. Could be an element of more than one, but it's an element of at least one. Say Q1 is the (or rather "a") quarter containing p. Now p is an element of some quarter of Q1; say Q2 is one of the quarters of Q1 with p in Q2. And say Q3 is one of the quarters of Q2, with p in Q3. Etc. Now the construction actually gives a certain interval I1 contained in [0,1] such that I1 gets mapped into Q1; I is one of the intervals [0,1/4], [1/4, 1/2,],[1/2, 3/4], 3/4,1]. In particular I1 is an interval of length 1/4, being one of the quarters of [0,1]. And there exists an interval I2 contained in I1, such that I2 has side length 1/16, and such that I2 gets mapped into Q2. Etc. (I said "into", not "onto", here.) Now I1, I2, ... is a nested sequence of closed and bounded intervals with side length decreasing to 1. Hence the intersection of this sequence of intevals contains exactly one point t. And that's the point that gets mapped to p by our curve. (Because that point gets mapped to a point which is in all the squares Q1, Q2, ... and p is the only such point.) >> > and what the limit is? Similarly, is there a decision >> >procedure to determine whether or not a point is on the curve? > >> In general I don't think so. (Although exactly >> what this even means is not as clear as you might >> think - real numbers are not the sort of things you >> can describe in finite terms suitable for plugging >> into a "procedure".) But for example I don't think >> there's a procedure for deciding whether a given >> construction analogous to the above, or >> equivalently, defined by some infinite series, >> actually defines a space-filling curve. > >Well, I guess either a turing machine or maybe a machine that can compute >directly with reals (I think this idea is due to Smale and some others?). The problem with a Turing machine is that there's no way to specify an arbitrary real number with a finite amount of tape. I've never heard of "a machine that can compute directly with reals" - I don't see how there could be such a machine, if we're talking about an actual physical machine that someone can build. If we're just talking about some abstract "machine" that can't actually be built then yes one of those could probably be used. But in that case I don't really see how we get a decision "procedure". If we're postulating abstract "machines" that can manipulate reals "directly" I don't see why we can't just as well say "check whether there's a real t with gamma(t)=p" for our "decision procedure"... >But I expect that you're right, there's probably no way to do it general. > >Thanks, >Dan Goodman > ============================================================================== From: hook@nas.nasa.gov (Ed Hook) Subject: Re: Peano space filling curve Date: 18 Aug 2000 15:10:45 GMT Newsgroups: sci.math In article <966561027.1761.0.nnrp-08.9e989aee@news.demon.co.uk>, "Dan Goodman" writes: |> > Now those curves approach |> > something as n -> infinity. That |> > something is a curve, and it intersects |> > every one of the subsquares of S at |> > every level - so it must in fact pass |> > through every point of S. |> |> OK, I follow the construction so far, but I don't follow this last step. I |> can see that it will intersect each square at every level, but every point |> on the side of each of these squares has at least one coordinate (x or y) |> that is 2^-n for some n, so would a point like, for instance |> (1/sqrt(2),1/sqrt(2)) be mapped onto? The fundamental fact that you need here is given by: Theorem. If { F_k | k in N } is a nested sequence of nonempty closed subsets of a complete metric space such that lim_{k --> \infinity} diam(F_k) = 0, then the intersection of this collection is a singleton set. (The assumption about the diameters implies that there can't be _more_ than one point in the intersection. To show that there's at least one point, pick points x_n in F_n for all n -- that gives a Cauchy sequence that is [eventually] in every F_k -- completeness says this sequence converges and the limit has to lie in the intersection.) All of the "geometric" constructions of a space-filling curve proceed by defining a sequence of partitions of [0,1]x[0,1], a corresponding sequence of partitions of [0,1] and, for each n in N, a map f_n: [0,1] --> [0,1]x[0,1] that sends the n'th partition of [0,1] into the n'th partition of [0,1]x[0,1]. (I haven't defined what that last requirement actually means, but I hope it's clear :-) Furthermore, the n'th partition is a refinement of the (n-1)'st partition for both the interval and the square _and_ the meshes of these partition decrease monotonically to 0. Given any point p in the square, it determines a nested sequence of closed subsets of [0,1]x[0,1] -- the n'th set in the sequence is one of the sets in in the n'th partition that contains the given point and we're careful to choose so that the sequence we end up with is nested. Using the maps f_n, this nested sequence of subsets of the square determines a nested sequence of subsets of [0,1] -- it's then easy to verify that the latter sequence satisfies the hypotheses of the Theorem above. And then f(x) = p if x is the point of [0,1] whose existence is guaranteed by the Theorem (and f is our space-filling curve). -- Ed Hook | Copula eam, se non posit Computer Sciences Corporation | acceptera jocularum. NAS, NASA Ames Research Center | All opinions herein expressed are Internet: hook@nas.nasa.gov | mine alone