1

私はこれが間違っていることを知っていますが、この問題を解決する正しい方法を考えることができません. 以下の12点で取り組んでいます。(1,2)(1,11)(7,8)(9,9)(12,13)​​、(13,4)、(20,8)、(22,3)、(23,12)、 (24,14),(26,7),(31,10)

これを2つのサブセットに分けます

左 = (1,2)(1,11)(7,8)(9,9)(12,13)​​,(13,4)

右=(20,8)、(22,3)、(23,12)、(24,14)、(26,7)、(31,10)

さらに切り詰める

LLeft=(1,2)(1,11)(7,8)

RLeft=(9,9)(12,13)​​,(13,4)

LRight=(20,8),(22,3),(23,12)

RRight=(24,14),(26,7),(31,10)

各セットの最小距離を見つけます。

左 (1,2)(1,11) は 9、(1,11)(7,8) は 6.7、(1,2)(7,8) は 8.48

最小は 6.7

RLeft (9,9)(12,3) は 6.70、(9,9)(13,4) は 6.4、(12,3)(13,4) は 1.14

最小値は 1.14 です

L右 (20,8)(22,3) は 5.38 (20,8)(23,2) は 5、(22,3)(23,12) は 9.05

最小は 5

R右 (24,14)(26,7) は 7.28 (24,14)(31,10) は 8.06 (26,7)(31,10) は 5.83

最小値は 5.83 です

これで、LLeft、RLeft、LRight、および RRight ができました。私が見つける必要があるのは、LRLeft、RLLEft_Right (中央の値)、および LRRight です。ここで混乱します。LRLeft を取得する唯一の方法は、LLeft と RLEft のすべての点を取り、2 つの間の距離を見つけることです。次に、その距離を使用して LLeft と RLeft と比較すると、左側の 2 点間の最短距離が得られます。次に、右と中央についても同じことを行います。それを行うためのより迅速でより良い方法があると確信していますが、それを理解することはできません。

4

1 に答える 1

3

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_caseをご覧ください。

ステップ4のより良いリソースがありますが、始めるために：再帰で、すでに最小距離がd1ありd2、それぞれ左と右のセット内にある場合、より近いポイントのペアがある場合-1つは左からであり、 1つは正しいセットからのものです。次にd、分割線の距離内のポイントをチェックするだけで済みます。ここで、 d = min(d1,d2)。

于 2011-04-24T10:42:00.370 に答える