Some combinatorial applications of spacefilling curves

The spacefilling curve suggests a heuristic tour of a set of points

Figure 1: A heuristic solution to the Traveling Salesman Problem is to visit the points in the same sequence as the Sierpinski spacefilling curve.

A spacefilling curve is a continuous mapping from a lower-dimensional space into a higher-dimensional one. A famous spacefilling curve is that due to Sierpinski, which is formed by repeatedly copying and shrinking a simple pattern (the convoluted tour in Figure 1).

A useful property of a spacefilling curve is that it tends to visit all the points in a region once it has entered that region. Thus points that are close together in the plane will tend to be close together in appearance along the curve.

This forms the basis of the heuristic, invented by L. Platzman and me, to produce a reasonably short tour of n given locations (the so-called Travelling Salesman's Tour): Simply visit them in the same sequence as does the spacefilling curve. For example, a short tour of the points marked in read is indicated by the green lines, which connect the points in the same sequence as their appearance on the spacefilling curve.

The spacefilling curve heuristic (SFC) has many advantages, if you are willing to accept solutions that are about 25% longer than optimum (expected, for random point sets). These advantages include:

The spacefilling curve heuristic has been used in many applications, including:

The idea of routing by spacefilling curve has subsequently been incorporated into the ARC/Info Geographical Information System, the CAPS Logistics Toolkit of Baan Systems, and other commercial systems managing 2-dimensional data.

A summary of the ideas, minus technical details but with pointers to technical literature, may be found in my class notes A routing system based on spacefilling curves [pdf format, 22 pages]. To accompany this is a table of Sierpinski indices of the points of a 100 x 100 grid [pdf format, 22 pages], with which you can set up your own routing system in an afternoon. Technical details about algorithm performance, along with citations to related work, may be found in “Spacefilling curves and the planar travelling salesman problem” with L. K. Platzman, Journal of the Association for Computing Machinery 36(4):719-737 (1989).

The spacefilling curve solution to the problem of visiting 15,112 cities in Germany

Figure 2: A TSP tour of 15,112 cities in Germany. This tour was induced by the Sierpinski spacefilling curve in less than a second and is about 1/3 again as long as the shortest possible.

It is interesting to compare this lightweight heuristic with a heavy-duty optimization package, such as the one developed by D. Applegate, R. Bixby, V. Chvatal, and W. Cook. Their TSP package is a tour-de-force of mathematical optimization technology and it has been used to solve a traveling salesman problem for 15,112 cities in Germany. This is the largest non-trivial problem for which a provably optimal solution has been generated. Applegate et al. describe the computational resources used: “The computation was carried out on a network of 110 processors located at Rice University and at Princeton University. The total computer time used in the computation was 22.6 years, scaled to a Compaq EV6 Alpha processor running at 500 MHz. The optimal tour has length 1,573,084 in the units used in TSPLIB; this translates to a trip of approximately 66,000 kilometers through Germany.”

For comparison, Paul Goldsman used the spacefilling curve heuristic to solve the same instance. Our solution was about 34% longer (Figure 2). At a leisurely 600 km of travel per day this means the total driving time would be about 147 days versus 110 days. But our computation took less than a second on a cheap laptop. So here is the tradeoff: Use our heuristic and you get a route immediately, but you must travel for an extra month. Alternatively, configure a network of 110 processors and spend two months to compute the shortest route — to save a month of driving.

A triangulated irregular network in which the triangles have been sequenced to form a path

Figure 3: All the points of a triangulated irregular network can be indexed continuously by finding a Hamiltonian path or circuit of the triangles and filling each with a suitably-oriented spacefilling curve.

Bill Nulty, Paul Goldsman, and I have extended some of these ideas in several directions: