Some NP-complete geometric problems

作者：Michael R. Garey, Ron L. Graham, David Johnson · 年份：1976 · DOI：10.1145/800113.803626 · 被引用次数：399 · 研究领域：Computational Geometry and Mesh Generation、Data Management and Algorithms、Digital Image Processing Techniques

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.