5つの別々のポイント間の最大距離を見つける

既知の効率的なアルゴリズムはありませんが（Doug Mのコメントを参照）、ユークリッド距離を見つけるよりも簡単な方法で解決できます。特に、ノルムの次のプロパティを使用します。

しましょう $d^p_{i,j}$ ポイント間のpノルム距離である $i$ そして $j$（技術的になりたい場合は、これらの2つの点を引くことによって形成されるベクトルのpノルムです）。一般的にこれを証明することはできないので、pを1または2に制限しましょう。$i,j$ と任意 $p$、 $d^p_{i,j}$ が最大の場合、すべての場合に最大になります $p$。

実際には、これは1ノルムを計算できることを意味します。これははるかに簡単です。1ノルムは次のようになります。

$$d^1_{i,j} = |x_i-x_j| + |y_i - y_j|$$

したがって、計算上は、（2ノルムを使用して）2つの減算、2乗、合計、および平方根ではなく、2つの減算、場合によっては否定、および合計を実行する必要があります。

最高の1ノルムを探してから、単一の2ノルムのみを計算します。

これは現在未解決の問題であり、Planar Euclidean MaximumTSPです。

に最適な線形時間アルゴリズムが存在します $\mathbb{R}^2$ とともに $L_1$-ノルム（[1]の定理3を参照）。

最大TSPはNP困難として知られています $\mathbb{R}^3$ ユークリッドノルムを使用します（[1]の定理4を参照）。

[1]：幾何学的最大巡回セールスマン問題（arxiv）

---

または、平面の点のセットの直径を尋ねることもできます。

この場合、回転キャリパー法が最適です$O(n \log n)$ アルゴリズム。

個々の比較を高速化するために、2乗ユークリッドノルムを使用できます。