6

最近接対点問題の説明をいろいろな文献で把握しようとしています。分割・解決・結合（分割して征服）、線形時間マージ（結合・征服）という基本的なアプローチはどれも同じですが、実際の実装は記事や本によって微妙に異なります。

ここでは、比較するポイントの数を制限しようとする線形時間マージが重要です。

Kleinberg bookでポイントが考慮されている方法は、このWikipedia の記事またはCormen bookでポイントが考慮されている方法とは少し異なります。

とにかく、後の 2 つについては、考慮すべき点の数について、ここ と ここ 、およびその他の多くの点について適切な説明を見つけることができます。

手元の問題については、 Kleinberg bookのこれらのスライド(スライド 32) をご覧ください。の主張は同じスライドにあります。より詳細な説明は、6 ページのセクション 6.2.5.6 にあります。11 point gap

しかし、上記のスライドの同じページ (スライド 32) には、 「12 を 7 に置き換えてもなお正しい」というような主張があります。

上記の主張の説明を見つけることができませんでした。

下の図を見てください。

ここに画像の説明を入力

赤い点を右半分と比較すると、右半分の点は網掛けの半円の中にあるはずです。極端なものを青にしようとしました。それでも、それらは |5-(-2)|+1 = 8 および |5-15|+1 = 11 離れています。

ここで何が欠けているのでしょうか？

4

3 に答える 3

1

実際には、ポイントの下半分の距離を計算する必要はありません。範囲内で、y 軸に従って並べ替えられたポイントを考慮すると、下から開始して、その上の領域のポイントのみを考慮して上に移動するためです。

于 2013-10-26T08:51:02.077 に答える
0

実際には、グリッド上に 9 つのポイントを配置できます。(0,0) が中心で、delta=1 と仮定すると、(-1,-1)、(-1,0)、...、(1,1) に 9 つのポイントを持つことができます。

せいぜい 9 であることの証明:

最適なパッキングでも、すべての中心が 2X2 の正方形の内側にあり、それぞれが半径 (1/2) の 3 層の円しか持つことができません。

したがって、この後、差は 8 に減少します。7 に到達するには、それが特別な場合ではないと仮定する必要があります (専門用語を忘れてしまいましたが、これは計算幾何学でよく使われる仮定です。また、3 点が同じ線上にないことも述べています。 「一般性仮定」とか。

于 2013-03-27T20:31:23.670 に答える