Spacefilling curves and the planar travelling salesman problem

DOI10.1145/76359.76361zbMath0697.68047OpenAlexW1966612958MaRDI QIDQ3474889

L. K. Platzman, John J. III Bartholdi

Publication date: 1989

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/76359.76361

zbMATH Keywords

fractal geometrysequencing and schedulingspacefilling curvesrouting and layout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (32)

Constructing competitive tours from local information ⋮ Indian kolam patterns, sand drawings in the Vanuatu Islands, the Sierpiński curve, and monoid morphisms ⋮ Novel concave hull-based heuristic algorithm for TSP ⋮ Neural methods for the traveling salesman problem: Insights from operations research ⋮ Compact Hilbert indices: space-filling curves for domains with unequal side lengths ⋮ A distribution-free TSP tour length estimation model for random graphs ⋮ Practical distribution-sensitive point location in triangulations ⋮ On properties of geometric random problems in the plane ⋮ Solving large-scale TSP using a fast wedging insertion partitioning approach ⋮ Submodularity and the traveling salesman problem ⋮ Assouad-Nagata dimension and gap for ordered metric spaces ⋮ Universal Algorithms for Clustering Problems ⋮ Sampling multidimensional signals by a new class of quasi-random sequences ⋮ Van der Corput and Golden Ratio Sequences Along the Hilbert Space-Filling Curve ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ An information global minimization algorithm using the local improvement technique ⋮ Algorithms for the universal and a priori TSP ⋮ Division rules for tissue P systems inspired by space filling curves ⋮ Applications of the space — filling curves with data driven measure — preserving property ⋮ The Guilty net for the traveling salesman problem ⋮ Sorting methods and convergence rates for Array-RQMC: some empirical comparisons ⋮ Lipschitz and Hölder global optimization using space-filling curves ⋮ Match twice and stitch: a new TSP tour construction heuristic. ⋮ Bounds for the traveling salesman paths of two-dimensional modular lattices ⋮ Reptilings and space-filling curves for acute triangles ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Nearest-neighbor graphs on the cantor set ⋮ Routing heuristics for automated pick and place machines ⋮ Efficacy of spacefilling heuristics in Euclidean combinatorial optimization ⋮ Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem ⋮ Strict s-numbers of non-compact Sobolev embeddings into continuous functions ⋮ ``Conscientious neural nets for tour construction in the traveling salesman problem: The vigilant net

This page was built for publication: Spacefilling curves and the planar travelling salesman problem