Some combinatorial applications of spacefilling curves
www2.isye.gatech.edu
Some combinatorial applications of spacefilling curves
1–10 of 19 posts
Re: Some combinatorial applications of spacefilling curves
#2Space 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.
Re: Some combinatorial applications of spacefilling curves
#3Space-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.
Re: Some combinatorial applications of spacefilling curves
#4Neat!
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.
Re: Some combinatorial applications of spacefilling curves
#5> 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.
Re: Some combinatorial applications of spacefilling curves
#6space 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
Re: Some combinatorial applications of spacefilling curves
#7Are 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?
Re: Some combinatorial applications of spacefilling curves
#8Are 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?
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?
Re: Some combinatorial applications of spacefilling curves
#9Are 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?
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.
Re: Some combinatorial applications of spacefilling curves
#10Are 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?
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?