0

I've created an (iterative) algorithm that generates a custom space-filling curve of a degree $n$, where each produced curve is made up of $(3^n)^2$ points and each point is only represented once within each curve.

The core concept is very similar to the one shown in Ex.1 and while the shape of the curve is slightly different, it still fulfills the qualities of a space-filling curve.

Ex.1: Peano curve

Although I'm certain that my algorithm produces the correct shape for each degree, I would like to prove it somehow. Since each curve consists of the smaller curves, I thought that induction would be an optimal way to do so, however I'm currently a little stuck as to how I would need to proceed about it.

I'm aware of the fact that induction would require me to prove that certain characteristics hold for every curve of the degree $n$, however the only criteria I could think of, are that each curve of the degree $n$ contains $(3^n)^2$ points, all points are placed horizontally or vertically within of each other, and none of the points are more than $1$ unit of distance away from each other.

Utilizing these criteria would lead to a very weak proof in my opinion, as the curve could fulfill these without necessarily abiding by the required shape, where it consists of smaller variants of the given curve.

Is there something I'm missing here and would proof via induction even be possible in such scenario?

Any answers would be greatly appreciated! Thank you in advance

Izaak van Dongen
  • 3,791
orb-livan
  • 1
  • Hello! It's great that you're interested in space-filling curves. I'm afraid your question is currently a bit too vague for this site, and it looks like you are (mis)-using some technical terminology that you are not very familiar with. Space-filling curves are continuous surjective maps from $[0, 1]$ to a hypercube, and I'm not sure if that's what you actually want to ask about. It would be very helpful to include the definition of your curve(s) (and maybe pictures) and explain what you mean by "correctness". Do you mean that when iterated, your curves get arbitrarily close to each point? – Izaak van Dongen Jul 21 '22 at 14:40
  • Hey, thank you so much for responding. I'm really sorry that my question is too vague, hopefully I'm able to clear some things up. The space-filling curve in question is a two-dimensional peano-meander-curve, which is described in this book: Michael Bader. Space-Filling Curves – An Introduction with Applications in Scientific Computing. Springer, 2013. The first 3 degrees of the curve can be seen in the following link: https://imgur.com/a/8fXYl5a. My algorithm constructs a curve for any given n. The corectness of any curve for a given n would require a formal proof – orb-livan Jul 21 '22 at 14:54
  • So when you say "correctness of a curve for a given $n$", do you mean you wish to prove that the curve your algorithm produces for input $n$ is the same curve as the one defined by your book? Or do you want to prove that the curve your algorithm produces has some property, like "for each point of the square, there's a point on the curve which is a distance of at most $3^{-n} \sqrt 2/2$ units away." - or something else? Ideally your question would be phrased as "here are some definitions, here is exactly what I want to prove about them, here's what I've tried, what should I do differently?" – Izaak van Dongen Jul 21 '22 at 15:08
  • Both options apply in my case. I would like to (if possible) formally prove that any produced curve of a degree n is valid due to certain characteristics it possesses. The issue is that I'm having trouble coming up with characteristics beyond verifying 1: the exact amount of points and 2: the distance between them, which would obviously not suffice, as these don't verify the shape of the curve in any form. This makes me question whether or not proof via induction is even suitable for this kind of problem. Hopefully this makes sense, thank you once again for editing and replying. – orb-livan Jul 21 '22 at 15:20

0 Answers0