マンハッタン距離が気になります。それは非常に具体的で、（それが良い言葉かどうかはわかりませんが）単純です。たとえば、このメトリックでnポイントのセットが与えられた場合、線形時間で2つの最も遠いポイント間の距離を見つけるのは非常に簡単です。しかし、2つの最も近いポイントを見つけることも簡単ですか？
任意のメトリックで最も近い2つのポイントを見つけるためのユニバーサルアルゴリズムが存在すると聞きましたが、それは複雑です。この状況（マンハッタン距離）で、この距離の特別なプロパティを使用して、より簡単なアルゴリズムを考え出すことができるかどうか疑問に思っています。これにより、実装がより簡単になりますか？
編集：平面上のn点。すべての点について、-10 ^ 9 <= x、y <= 10^9とします。