Spacefilling Curves and the Planer Travelling Salesman Problem. Revision.

Abstract

This paper analyzes the performance of a novel heuristic to obtain the minimal-length tour of N given points in the plane: they are sequenced as they appear along a spacefilling curve. The algorithm consists essentially of sorting, so it is easily coded and requires only O(N) memory and O(N log N) operations. Its performance is shown to be competitive with that of other available methods. Key words: Planar travelling salesman problem, heuristic algorithm, spacefilling curve.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1984
Accession Number
ADA149337

Entities

People

  • J. J. Bartholdi Iii
  • L. K. Platzman

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Air Platforms
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Bits
  • Computer Programming
  • Computers
  • Engineering
  • Geometry
  • Heuristic Methods
  • Intervals
  • Monte Carlo Method
  • New York
  • Random Variables
  • Right Angles
  • Sequences
  • Simulations
  • Systems Engineering
  • Triangles
  • Two Dimensional

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.
  • Operations Research