GoKawiilSome combinatorial applications of spacefilling curves
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 SFC algorithm is fast: Only O( n log n ) effort to construct a tour of n points and only O(log n ) effort to update the solution by adding or removing points.
log ) effort to construct a tour of points and only O(log ) effort to update the solution by adding or removing points. The SFC heuristic does not need explicit distances between points and so there is no need to compute or measure these, as most other heuristics must.
The algorithm is parallelizable. (In comparison, the comparable algorithm, Nearest Neighbor, is apparently not parallelizable.)
parallelizable.) The length of links in the SFC tour of random points is expected to be small and of small variance, so that (1/k)-th of the stops account for about (1/k)-th of the travel time. This means that an SFC tour can easily be converted to tours for k vehicles simply by partitioning the SFC route into k segments.
The spacefilling curve heuristic has been used in many applications, including:
... continue reading