ポイントのセットからマンハッタン距離/直線距離の合計が最小のポイントを見つけたい（つまり、このポイントとセット内の各ポイントの間の直線距離の合計が最小である必要があります）。結果のポイントは、指定されたセットのポイントの1つになる可能性があります（必ずしもそうとは限りません）。同じ最小距離で複数のポイントが存在する場合は、それらすべてを取得したいと思います。
言い換えると：
特定の交差点がマークされたグリッドがあります。マークされたすべての交差点に最も近い交差点を見つけたいのですが。つまり、すべての点からの距離の合計が最小になるような点を見つける必要があります。
マンハッタン距離の優れた点は、距離自体が 2 つの独立した要素 (x 座標と y 座標の距離) で構成されていることです。したがって、2 つの単純なタスクを解決し、それらの結果をマージして目的の結果を得ることができます。
私が話しているタスクは次のとおりです。線上の点が与えられます。すべての点までの絶対距離の合計を最小にする直線上の点を見つけます。多数ある場合は、それらすべてを見つけます (ちなみに、それらは常に証明が容易な単一のセグメントになります)。セグメントは、セットの (場合によっては 2 つの) ポイントの中央値によって決定されます。中央値とは、左右に同じ数のポイントがあるポイントを意味します。点の数が偶数の場合、そのような点はなく、両方向の差が 1 の点を選択して線分を形成します。
ここに、この単純なタスクの解決策の例を追加します。
線上の点がそのような場合：
-4 | | | 0 | 2 3 4
^
解決策は単なる点であり、それは2.
線上の点がそのような場合：
-4 | | | 0 | 2 3
^---^
セグメント全体 [0, 2] が問題の解です。
このタスクをxとy座標について個別に解決し、結果をマージして最小距離の点の四角形を取得します。
セットまでのマンハッタン距離が最小であるポイントを見つけたいと想像してください(0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)
次の 2 つの単純なタスクを作成します。
x の場合:
0 1 2 3 3 4
^-^
そして、ここで解決策がセグメントです[2, 3](ここで point が複製されていることに注意してください3。これは、おそらく最も直感的な方法ではありません)。
Yについて：
3 3 4 5 6 7
^-^
ここでの解決策はセグメント[4, 5]です。
最後に、最初のタスクの解は次の式の長方形であることがわかります。
2 <= x <= 3; 4 <= y <= 5
複雑さについて話しましょう。
タスクの複雑さは、実際には単純なタスクを解決する複雑さと同じです (既に説明したように、ソリューションは実際には 2 つの単純なタスクを解決することで構成されるため)。多くの人は、ソートして中央値を選択することで解決します。ただし、これにより、入力セット内のポイント数がO(nlog n)複雑になります。n
これは、k 番目の要素を見つけるためのより優れたアルゴリズムを使用すると改善できます ( C++ STL での実装例)。このアルゴリズムは、基本的に qsort と同じアプローチに従います。実行時間はO(n)です。中央値が 2 つの場合でも、これは依然として線形のままであるため (同じアルゴリズムを 2 回実行する必要があります)、アルゴリズムの全体的な複雑さは になりO(n)ます。入力自体が前述の複雑さである限り、タスクをこれ以上速く解決できないことは明らかです。