Spacefilling curves and the planar travelling salesman problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spacefilling curves and the planar travelling salesman problem

Full text

Pdf (1.21 MB)

Source

Journal of the ACM (JACM) archive
Volume 36 , Issue 4 (October 1989) table of contents

Pages: 719 - 737

Year of Publication: 1989

ISSN:0004-5411

Authors

Loren K. Platzman	Georgia Institute of Technology, Atlanta
John J. Bartholdi, III	Georgia Institute of Technology, Atlanta

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 101, Citation Count: 10

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/76359.76361 What is a DOI?

ABSTRACT

To construct a short tour through points in the plane, the points are sequenced as they appear along a spacefilling curve. This heuristic consists essentially of sorting, so it is easily coded and requires only O(N) memory and O(N log N) operations. Its performance is competitive with that of other fast methods.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BARTHOLDI, J. J., AND PLATZMAN, L.K. An O(nlogn) planar travelling salesman heuristic based on spacefilling curves. Oper. Res. Lett. 1 (1982), 121-125.
	2	John J. Barthholdi, III , Loren K. Platzman, Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Science, v.34 n.3, p.291-305, March 1988 [doi>10.1287/mnsc.34.3.291]
	3	BARTHOLDI, J. J., PLATZMAN, L. K., COLLINS, R. L., AND WARDEN, W.H. A minimal technology routing system for meals-on-wheels. InterJaces 13 (1983), 1-8.
	4	BEARDWOOD, J., HALTON, J. H., AND HAMMERSLEY, J. The shortest path through many points. Proc. Cambridge Philosophical Soc. 55 (1959), 299-327.
	5	BENTLEY, J. L. A case study in applied algorithm design. IEEE Trans. Comput. 33 (1984), 75-88.
	6	BERTSIMAS, D., AND GR~GN~, M. On the spacefilling curve heuristic for the Euclidean travelling salesman problem. Oper. Res. Lett., to appear.
	7	JOHNSON, D. S., MCGEOCH, L. A., AND ROTHBERG, E. E. Near-optimal solutions to very large traveling salesman problems. To appear.
	8	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	9	MANDELBROT, B.B. The Fractal Geometry of Nature. Freeman, New York, 1983.
	10	PAPADIMITRIOU, C. H. The Euclidean travelling salesman problem is NP-complete. Theoret. Compttt. Sci. 4 (1977), 237-244.
	11	STEELE, J. M. Complete convergence of short paths and Karp's algorithm for the TSP. Math. Oper. Res. 6 (1981), 374-378.
	12	STEELE, J.M. Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Prob. 9 ( 1981), 365-376.

CITED BY 10

	Pangfeng Liu , Sandeep N. Bhatt, Experiences with Parallel N-Body Simulation, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1306-1323, December 2000
	Nina Amenta , Sunghee Choi , Günter Rote, Incremental constructions con BRIO, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	John R. Pilkington , Scott B. Baden, Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.288-300, March 1996
	Aline C. Viana , Marcelo D. de Amorim , Serge Fdida , Yannis Viniotis , José F. de Rezende, Easily-managed and topology-independent location service for self-organizing networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	Guohua Jin , John Mellor-Crummey, SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.120-148, March 2005
	Mohammad T. Hajiaghayi , Robert Kleinberg , Tom Leighton, Improved lower and upper bounds for universal TSP in planar metrics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.649-658, January 22-26, 2006, Miami, Florida
	Lujun Jia , Guolong Lin , Guevara Noubir , Rajmohan Rajaraman , Ravi Sundaram, Universal approximations for TSP, Steiner tree, and set cover, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Keith Marsolo , Srinivasan Parthasarathy , Kotagiri Ramamohanarao, Structure-based querying of proteins using wavelets, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Chris H. Hamilton , Andrew Rau-Chaplin, Compact Hilbert indices: Space-filling curves for domains with unequal side lengths, Information Processing Letters, v.105 n.5, p.155-163, February, 2008
	Aline Carneiro Viana , Marcelo Dias de Amorim , Yannis Viniotis , Serge Fdida , Jose Ferreira de Rezende, Twins: A Dual Addressing Space Representation for Self-Organizing Networks, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1468-1481, December 2006

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
Subjects: Combinatorial algorithms

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sequencing and scheduling; Sorting and searching

General Terms:
Algorithms, Performance

REVIEW

"Benjamin L. Schwartz : Reviewer"

For the travelling salesman problem (TSP) on N cities the authors introduce a heuristic based on space-filling curves. They claim this is the first combinatorial application of fractal geometry. In practice, more...

Collaborative Colleagues:

Loren K. Platzman: colleagues

John J. Bartholdi, III: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player