Comments
Hacker News
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.
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?
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.
by shraiwi
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
by shoo
> 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.
by shoo
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?
by mkj
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.
by kmschaal
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?
by sfink
Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- 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.
- 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?
- 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.
by shraiwi - 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-treeby shoo
- > 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.
by shoo - 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?by mkj
- 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.by kmschaal
- 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?
by sfink