>>549
ヒント： ボロノイ図

3次元ボロノイ図の高速な近傍探索アルゴリズムが存在するのか知らないけど、
とりあえず適当なことを言ってみる。