Кривая, заполняющая пространство (spacefilling curve), непрерывно отображает линию в плоскость и «заходит» во все точки региона, почти не покидая его. На этом свойстве Л. Платцман и автор построили эвристику для задачи коммивояжёра: заданные точки просто обходятся в том порядке, в каком их посещает Sierpinski spacefilling curve. Получается маршрут примерно на 25% длиннее оптимального на случайных наборах, зато со множеством приятных бонусов.
Алгоритму нужно всего O(n log n) времени на построение тура из n точек и O(log n) на добавление или удаление точки. Ему не нужны явные расстояния — ни вычислять, ни измерять. Эвристика легко параллелится, чего не скажешь о сравнимом методе ближайшего соседа. Звенья маршрута короткие и имеют малый разброс по длине, поэтому (1/k)-я часть остановок даёт примерно (1/k)-ю часть времени поездки. Маршрут легко нарезается на k кусков и распределяется между k машинами.
Практических применений хватает. Для программы Meals-on-Wheels в округе Фултон (Атланта, Джорджия) на её основе собрали систему доставки сотен обедов в день — хватило двух картотек на rolodex. American Red Cross использовал SFC-маршрутизацию, чтобы доставлять кровь по больницам Атланты. Учёные из TRW Systems (подрядчик Strategic Defense Initiative — программы «Звёздные войны») выбрали эту эвристику для наведения космического лазера: она была хорошо проанализирована, параллелилась и работала на компьютере, пригодном для доставки на орбиту. М. Ири с коллегами из Токийского университета применили SFC к управлению перьевым плоттером для вычерчивания карт и сократили время отрисовки большого дорожного атласа с десяти часов до получаса. Идея затем встроилась в геоинформационную систему ARC/Info, транспортный инструментарий CAPS Logistics Toolkit от Baan Systems и другие коммерческие системы для двумерных данных.
Насколько эвристика легковесна, показывает сравнение с убойным оптимизационным пакетом от D. Applegate, R. Bixby, V. Chvatal и W. Cook. Они нашли доказуемо кратчайший тур для 15 112 городов Германии — потребовалось 110 процессоров и 22,6 года процессорного времени в пересчёте на Compaq EV6 Alpha 500 МГц. Длина оптимального маршрута — около 66 000 км. А Пол Голдсман на дешёвом ноутбуке построил SFC-тур для той же задачи меньше чем за секунду. Он оказался на 34% длиннее: около 147 дней за рулём против 110, если ехать неспешные 600 км в день. Выбор такой: либо мгновенный маршрут и лишний месяц в пути, либо два месяца считать кратчайший тур на кластере, чтобы сэкономить месяц езды. Позже Билл Нулти, Пол Голдсман и автор распространили идеи на триангулированные нерегулярные сети, непрерывно индексируя точки через гамильтоновы пути треугольников и подходяще ориентированные spacefilling curves.