Spacefilling Curves and Routing Problems in the Plane,

Abstract

This paper introduces a novel heuristic to compute a 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: it is easily coded, requires only O (N) memory, and may be implemented to execute in O (N log N) operations at most, or O (N) operations on the average.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 11, 1983
Accession Number
ADA126309

Entities

People

  • John J. Bartholdi Iii
  • Loren K. Platzman

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Engineering
  • Intervals
  • Mathematics
  • Military Research
  • Numbers
  • Operations Research
  • Probability
  • Random Variables
  • Real Variables
  • Sequences
  • Square Roots
  • Theorems
  • Triangles
  • Two Dimensional

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Electromagnetic Wave Scattering and Antenna Radiation Engineering
  • Operations Research