Some combinatorial applications of spacefilling curves

Posted by shraiwi 2 days ago

Counter64Comment17OpenOriginal

Comments

Comment by sfink 2 hours ago

Why 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?

Comment by mkj 3 hours ago

A 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?

Comment by zX41ZdbW 2 hours ago

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.

Comment by mkj 1 hour ago

Aha, thanks. The adsb.exposed maps are excellent, thank you! Really intrigued by the building maps.

Comment by kmschaal 9 hours ago

Space-filling curves as a traveling salesman heuristic is a really nice application I was not aware of. I have mostly seen them in the context of domain decomposition for parallel computing, where you cut the curve at n points to obtain n+1 disjoint domains.

Comment by shoo 8 hours ago

> To target a space-based laser for the Strategic Defense Iniative (commonly known as the "Star Wars" program)

I'm guessing this application would be selecting an ordering to engage multiple simultaneous targets in minimal-ish time - MIRV warheads or missiles launched in a barrage.

Comment by shoo 8 hours ago

space filling curves can also be used under the hood in data structures that support efficient spatial queries: https://en.wikipedia.org/wiki/Hilbert_R-tree

Comment by galactushonor 6 hours 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?

Comment by imurray 4 hours ago

John 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/ -- the manual describes how (pdftex will make a nice pdf), with further references, and C code is available.

Comment by nkrisc 5 hours ago

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?

Comment by alecst 4 hours ago

Well, how would you walk along a curve like that?

Comment by nkrisc 1 hour ago

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.

Comment by sfink 1 hour ago

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.

Comment by shraiwi 2 days ago

Space filling curves can be used to compute good TSP tours in O(n log n) time and linear space.

This describes an implementation using a Rolodex to plan Meals on Wheels routes.

Comment by akoboldfrying 9 hours ago

Neat!

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 decreases the total tour length, and every such decrease is lower-bounded by the smallest such decrease among all (nCities choose 4) possible sets of 4 cities, repeatedly doing this must eventually terminate in a crossing-free tour.

Comment by sfink 16 minutes ago

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?