2
$\begingroup$

Are there any 3D hilbert curves wherein there are no double-length edges?

An example of a "double-length edge" would be the two sections outlined in red below:

enter image description here

$\endgroup$
  • $\begingroup$ It's unclear what this question means since what you are drawing is only a finite approximation to a Hilbert curve. Actual Peano-Hilbert curves tend to be nowhere differentiable, so they do not contain any "edges". $\endgroup$ – Moishe Kohan Aug 31 '17 at 6:21
  • $\begingroup$ @MoisheCohen I assume the question means something like this: For all $n$, is there a Hamiltonian path $P_n$ on a cubic grid with $2^n$ vertices along each edge, such that $P_n$ contains no straight line across $3$ vertices, and such that every $P_{n+1}$ refines $P_n$ in the same way as the construction of the standard 3D Hilbert curve? $\endgroup$ – Chris Culter Aug 31 '17 at 7:48
  • $\begingroup$ @ChrisCulter This is a correct assumption. $\endgroup$ – CoryG Aug 31 '17 at 13:19
  • $\begingroup$ @CoryG: And this still does not make sense to me. As I said, this $P_n$ is not the curve itself and you can use non-grid paths to approximate the same curve. $\endgroup$ – Moishe Kohan Sep 1 '17 at 5:04
4
$\begingroup$

In 3D, there are only three seven-segment polylines with vertices at the vertices of the unit cube and all segments axis-aligned, if we ignore their rotated and/or mirrored copies: Three 2×2×2 curves

The middle one in black is the basic 3D Hilbert curve.

The left one in blue is similar to the basic 3D Hilbert curve, except that the copy in the third dimension is rotated by 90°. This causes the end point to be diagonally opposite to the initial point, which makes this one difficult to use.

The right one in red has no 2D equivalent; it is a 3D primitive. If closed, it matches the closed Hilbert curve, so in some sense it is a permutation of the 3D Hilbert curve (i.e., with a different open edge).

As far as I understand, none of the above recursively produce a space-filling curve without two consecutive line segments being parallel.

However, if we replace each edge in the middle/black curve with rotated (red) and rotated and mirrored (purple) copies of the right/red block, we get a $4 \times 4 \times 4$ curve, with no consecutive parallel line segments: Mixed curve

I do suspect that this approach does generalize (that is, one could replace each purple or red edge with a rotated and/or mirrored copy of the middle/black block, and get a $8 \times 8 \times 8$ curve with no consecutive parallel line segments; and so on for any $2^n \times 2^n \times 2^n$ lattice), but I have not verified this: I've only examined curves that fill a $4 \times 4 \times 4$ lattice.

$\endgroup$
  • $\begingroup$ This is great, thank you. $\endgroup$ – CoryG Sep 2 '17 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.