Some combinatorial applications of spacefilling curves
8 hours ago
- A spacefilling curve is a continuous mapping from lower to higher dimensions, exemplified by the Sierpinski curve formed by repeating and shrinking a simple pattern.
- The curve visits all points in a region once it enters, so points close in the plane appear close along the curve, enabling a heuristic for the Traveling Salesman Problem (TSP).
- The spacefilling curve heuristic (SFC) visits points in the order they appear on the curve, producing tours about 25% longer than optimal for random point sets.
- SFC heuristic has advantages: simple implementation, fast computation, and suitability for dynamic or online routing; used in GIS, logistics, and commercial systems.
- Compared to optimal TSP solvers (e.g., for 15,112 German cities, needing 22.6 years on 110 processors), SFC yields a 34% longer tour but computes in under a second on a laptop.
- The tradeoff: SFC provides immediate routes at the cost of extra travel time, while optimal solutions require massive computational resources to save a month of driving.