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?
Some combinatorial applications of spacefilling curves
11–19 of 19 posts
Re: Some combinatorial applications of spacefilling curves
#12A few times I've had an irregular 2D dataset to process and thought "aha, maybe I can be lazy and iterate ordered by a space filling curve coordinates and it'll be more cache effective". But it's never given any improvement. Anyone tried something similar?
Re: Some combinatorial applications of spacefilling curves
#13Why O(n log n)? I guess I thought that mapping a coordinate to its distance from the start of a space filling curve would be a constant time operation, or rather, it would only be proportional to the number of bits in your coordinate system which is usually ignored in combinatorial analysis.
Because once you have that, you just need to sort simple integers, which you can do in linear time with a radix sort. (Again ignoring bit lengths.)
What am I missing?
Re: Some combinatorial applications of spacefilling curves
#14A few times I've had an irregular 2D dataset to process and thought "aha, maybe I can be lazy and iterate ordered by a space filling curve coordinates and it'll be more cache effective". But it's never given any improvement. Anyone tried something similar?
Yes, for example, the datasets at this page: https://adsb.exposed/ are indexed by the Morton curve: https://github.com/ClickHouse/adsb.exposed/#database-and-que... and https://reversedns.space/ as well.
Also, a trivial application is image compression. Let's say you have a PNG image. PNG uses zlib, so if instead you take a raw bitmap and compress it with ZSTD, it typically will be better, but if you also sort pixels by the Hilbert curve first and then compress with ZSTD, it will be typically even better.
Re: Some combinatorial applications of spacefilling curves
#15Earlier quoted context omitted.
Couldn't you just take any 2D space filling curve and extend it infinitely on the Z axis to make a space filling 3D surface?
Well, how would you walk along a curve like that?
Imagine 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.
Re: Some combinatorial applications of spacefilling curves
#16A few times I've had an irregular 2D dataset to process and thought "aha, maybe I can be lazy and iterate ordered by a space filling curve coordinates and it'll be more cache effective". But it's never given any improvement. Anyone tried something similar?
Yes, for example, the datasets at this page: https://adsb.exposed/ are indexed by the Morton curve: https://github.com/ClickHouse/adsb.exposed/#database-and-que... and https://reversedns.space/ as well. Also, a trivial application is image compression. Let's say you have a PNG image. PNG uses zlib, so if instead you take a raw bitmap and compress it with ZSTD, it typically will be better, but if you also sort pixels…
Aha, thanks. The adsb.exposed maps are excellent, thank you!
Really intrigued by the building maps.
Re: Some combinatorial applications of spacefilling curves
#17Earlier quoted context omitted.
Well, how would you walk along a curve like that?
Imagine 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.
Yes, 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.
Re: Some combinatorial applications of spacefilling curves
#18Neat! Another benefit I see is that you could quickly generate many heuristic solutions by randomly translating, rotating and/or uniformly scaling the curve, and then choose the best. It does look like it can produce crossing edges, which are suboptimal in Euclidean space, but these are easy to rectify -- whenever 2 edges cross, just swap their endpoints for a quick guaranteed improvement. Because doing this strictly…
That's the missing part in the article. The example of the TSP solution for all cities in Germany was a pretty poor one compared to the optimal, which immediately raises the question: how good is it if you do some simple tricks to improve the heuristic? Some simple global perturbations like you suggested, and then local improvements like swaps to remove crossings, or running it at multiple scales and taking the best result for each region, or whatever.
The space-filling curve approach strikes me as a decent way to get a starting point, not something to use unmodified. But I've no idea whether that's true -- does the structure of such a solution lend itself well to simple iterative improvements or not?
Re: Some combinatorial applications of spacefilling curves
#19Earlier quoted context omitted.
Imagine 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.
Yes, 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…
I see what you mean, I misunderstood initially.