• ベストアンサー

最近対点問題について質問です。

最近対点問題に置いて、距離最小になるp, q があるなら、両者は両点集合の 境界線からδ以内の距離にあり、その範囲内で調べる点は8点以内でよい。 とありますが、測定をユークリッド距離を使う場合とマンハッタン距離を使う場合で ちがいはあるのでしょうか? どちらを使っても8点でよいのでしょうか? よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

証明は確認してないけど. 「1辺の長さが δ の正方形の中に互いの距離が δ 以上であるように点を配置する」とか「辺の長さが δ×2δ の長方形の中に (以下同様)」とかからの結果じゃないかなぁ. もちろん「ユークリッド距離だと 7点もない」なんかはあるかもしれないけどね.

2009googoo
質問者

補足

ありがとうございます。 それと最近対点ではなく最近点対が正しいようで、もうしわけありません。 説明の「1辺の長さが δ の正方形の中に互いの距離が δ 以上であるように点を配置する」と「辺の長さが δ×2δ の長方形の中に (以下同様)」がユークリッド距離を使う場合とマンハッタン距離を使う場合とのちがいということでしょうか? よろしくお願いします。

関連するQ&A