2点間の距離の最大値を求めたい

n個の点から2点を選んだ時の2点間の距離の最大値を求めたいのです。 計算量 O（n^2） なら 出ますが もっと少ないアルゴリズムはありませんか。

No.3 ベストアンサー 回答者： stomachman 回答日時： 2021/01/28 20:49

No.2へのコメントについて。

> そうはいかないですよね。

ですね。

この回答へのお礼

重ねて回答ありがとうございました。
図示一発明瞭です。
逆に「O(n^2)を要する」の証明がほしくなります。
退散します。

お礼日時：2021/01/30 04:25

No.2 回答者： stomachman 回答日時： 2021/01/28 16:13

計算幾何学の話ですね。

>もっと少ないアルゴリズム
は知らんけど、とりあえず思いつくのは：
　n個の点の凸包ならO(n log n)でわかる。で、2点を結ぶ最長の線分の端は凸包の頂点に違いないから、凸包の頂点数mがnよりうんと少ないなら速くなりうる（けど、最悪n個が全部凸包の頂点という場合もある）。言い換えれば、n個の点の発生原理によっては、「平均的に速い」と言えるかも。

この回答へのお礼

回答ありがとうございます。
＞＞n個の点の凸包ならO(n log n)でわかる。
＞＞2点を結ぶ最長の線分の端は凸包の頂点に違いない
参考になります。
最悪で　O(n^2)は　避けられないように思います。
固定点Ａ1（選び方に工夫）からO(n)でｎ-1個の点までの距離を求めて
Ａ1からの最大距離点A2を得ていく
Ａ2からの最大距離点A3を得ていく
　.
Ａiからの最大距離点Ai+1を得ていく
同じ点に戻ったら　そこまでの最大距離の中に答えが
あったりして。O(n*i)となりO(n^2)より少なそうですが
そうはいかないですよね。

お礼日時：2021/01/28 20:40

No.1 回答者： yhr2 回答日時： 2021/01/26 09:27

＞計算量 O（n^2）

って、何の計算量ですか？

「距離を比べる」のだから、まず「距離を計算する」のは必須ですよね？
その後の「最大値を見つける」ところには、いろいろなアルゴルズムがあると思いますが。

選択アルゴリズム
https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E …