Some NP-complete geometric problems

ABSTRACT

We show that the STEINER TREE problem and TRAVELING SALESMAN problem for points in the plane are NP-complete when distances are measured either by the rectilinear (Manhattan) metric or by a natural discretized version of the Euclidean metric. Our proofs also indicate that the problems are NP-hard if the distance measure is the (unmodified) Euclidean metric. However, for reasons we discuss, there is some question as to whether these problems, or even the well-solved MINIMUM SPANNING TREE problem, are in NP when the distance measure is the Euclidean metric.

REFERENCES

• 1: A. V. Aho, M. R. Garey, and F. K. Hwang, "Rectilinear Steiner Trees: Efficient Special Case Algorithms", Networks (to appear).
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: W. M. Boyce and J. B. Seery, "STEINER 72, An Improved Version of Cockayne and Schiller's Program STEINER for the Minimal Network Program", Bell Laboratories Computing Science Technical Report #35 (1975).
• 4: E. J. Cockayne and D. G. Schiller, "Computation of Steiner Minimal Trees", in Combinatorics, D. J. A. Welsh and D. R. Woodall (eds.), Inst. Math. Appl., (1972) 53-71.
• 5: M. R. Garey, R. L. Graham, and D. S. Johnson, "The Complexity of Computing Steiner Minimal Trees", (to appear).
• 6: M. R. Garey and D. S. Johnson "The Rectilinear Steiner Tree Problem is NP-Complete", (to appear).
• 7: E. N. Gilbert and H. O. Pollak, "Steiner Minimal Trees", SIAM J. Appl. Math., 16 (1968) 1-29.
• 8: R. L. Graham, "Some Results on Steiner Minimal Trees", Bell Laboratories Technical Memorandum, (1967).
• 9: M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM J. Appl. Math., 14 (1966), 255-265.
• 10: S. Lin and B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem", BSTJ 21 (1973), 498-516.
• 11: R. M. Karp, "Reducibility Among Combinatorial Problems", in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York, 1972, 85-104.
• 12: R. M. Karp, "On the Computational Complexity of Combinatorial Problems", Networks, 5 (1975), 45-68.
• 13: Z. A. Melzak, "On the Problem of Steiner", Canad. Math. Bull., 4 (1961), 143-148.
• 14: M. H. A. Newman, Elements of the Topology of Plane Sets of Points, Cambridge University Press, Cambridge, (1964) 115-116.
• 15: A. M. Odlyzko, personal communication.
• 16: C. H. Papadimitriou, "The Euclidean Traveling Salesman Problem is NP-Complete", Princeton University Computer Science Technical Report No. 191 (1975).
• 17: D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, "Approximate Algorithms for the Traveling Salesperson Problem", 15th IEEE Annl. Symp. on Switching and Automata Theory, (1974), 33-42.
• 18: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 19: M. I. Shamos and D. Hoey, "Closest Point Problems", 16th Annl. Symp. on Foundations of Computer Science, IEEE, 1975, 151-162.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Theory