3 ms·
Are there higher dimensional analogues and generalization of space filling curves? Space filling surfaces (wrt 3D) or volumes (in 4D). Are they useful in any se
by galactushonor 2mo ago
Are there higher dimensional analogues and generalization of space filling curves? Space filling surfaces (wrt 3D) or volumes (in 4D). Are they useful in any sense?
- nkrisc 2mo agoCouldn't you just take any 2D space filling curve and extend it infinitely on the Z axis to make a space filling 3D surface?
- alecst 2mo agoWell, how would you walk along a curve like that?
- nkrisc 2mo agoImagine a sheet of paper folded in such a way that if you looked at it perfectly edge-on it would appear as a 2D Hilbert curve.
- sfink 2mo agoYes, that's understood, but it's not the point. That would convert a 3D space to a 2D space (the Z dimension is unaffected). But a 2D Hilbert curve converts 2D->1D, and a 3D Hilbert curve converts 3D->1D -- it's a curve winding its way through 3D space. (And yes, it certainly does exist and is used.) Any (quantized) point in 3D can be mapped to a distance from the start of the 3D Hilbert curve. But Hilbert curves are complicated. If you have n dimensions, you can simply take the sequence of bits describing the position in each dimension and interleave them, forming a longer sequence of bits. It's not nearly as nice of a curve -- adjacent points along the line are not necessarily close in n-dimensional space the way they would be with a Hilbert curve -- but it's simple to calculate and proves that you can generalize this stuff to any number of dimensions. This interleaving produces what is called a Z-curve or Morton curve. It's not continuous like the Hilbert curve, so mathematically you might not call it a space-filling curve but in CS-land, you probably would.
- nkrisc 2mo agoI see what you mean, I misunderstood initially.
- imurray 2mo agoJohn Skilling has used a generalization of the Hilbert curve to n-dimensions in his BayeSys software for Bayesian inference: https://www.inference.org.uk/bayesys/ https://www.inference.org.uk/bayesys/ -- the manual describes how (pdftex will make a nice pdf), with further references, and C code is available.
- knome 2mo agohttps://eisenwave.github.io/voxel-compression-docs/rle/hilbert_curves.html https://eisenwave.github.io/voxel-compression-docs/rle/hilbe...