Day 126-Q4 | Vantage-Point Tree（距離空間の最近傍探索）

問題

2次元平面上に $N$ 個の点があり、$i$ 番目の点の座標は $(x_i, y_i)$ である。$Q$ 個のクエリが与えられ、各クエリは座標 $(qx, qy)$ を指定するので、$N$ 個の点の中でユークリッド距離が最小となる点のインデックス（$1$-indexed。同点距離が複数ある場合は番号が最小のもの）を答えよ。

本問題は2次元ユークリッド空間で出題するが、Vantage-Point Treeは「距離の三角不等式さえ満たせば任意の距離関数に適用できる」点がk-d木との違いであることを意識して実装すること。座標の各軸を個別に見て分割するのではなく、距離そのものだけを使って分割する。

入力形式

N
x_1 y_1
...
x_N y_N
Q
qx_1 qy_1
...
qx_Q qy_Q

制約

$1 \le N \le 100000$

$1 \le Q \le 100000$

$-10^9 \le x_i, y_i, qx_j, qy_j \le 10^9$

座標はすべて整数

入出力例

入力例1

出力例1

1
2

クエリ1(1,1)に最も近いのは点1(0,0)。クエリ2(100,100)に最も近いのは点2(10,10)

概念図

ヒント（段階的開示）

ヒント1（方向性）

$N,Q\le10^5$の制約で愚直に各クエリごとに全点との距離を計算すると$O(NQ)$で間に合わない。k-d木は座標軸に強く依存する分割だが、より一般の距離空間（三角不等式さえ成り立てばよい）でも使える構造としてVantage-Point Tree (VP-Tree)を考える。

ヒント2（アプローチ）

点集合から1点を代表点として選び、残り全点との距離を計算する。その距離の中央値$m$を基準に、距離が$m$以下の点を左部分木、$m$より大きい点を右部分木として再帰分割する。最近傍探索では代表点との距離を計算し現在の最良距離を更新した上で、三角不等式により「反対側の部分木を探索する必要があるか」を$|d(q,\text{vp})-m|\le\text{best}$で判定する。

ヒント3（誘導）

def build(points):
    if not points:
        return None
    vp = points[0]
    rest = points[1:]
    if not rest:
        return {'vp': vp, 'radius': 0, 'left': None, 'right': None}
    dists = [dist(vp, p) for p in rest]
    median = sorted(dists)[len(dists) // 2]
    left = [p for p, d in zip(rest, dists) if d <= median]
    right = [p for p, d in zip(rest, dists) if d > median]
    return {'vp': vp, 'radius': median, 'left': build(left), 'right': build(right)}

模範解答 (Python)

import sys
import random
import math


def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    pts = []
    for i in range(n):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        pts.append((x, y, i))

    def dist2(a, b):
        dx = a[0] - b[0]
        dy = a[1] - b[1]
        return dx * dx + dy * dy

    random.seed(12345)
    sys.setrecursionlimit(300000)

    class Node:
        __slots__ = ('vp', 'radius2', 'left', 'right')

    def build(points):
        if not points:
            return None
        vp_idx = random.randrange(len(points))
        points[0], points[vp_idx] = points[vp_idx], points[0]
        vp = points[0]
        rest = points[1:]
        node = Node()
        node.vp = vp
        if not rest:
            node.radius2 = 0
            node.left = None
            node.right = None
            return node
        dists = [dist2(vp, p) for p in rest]
        order = sorted(range(len(rest)), key=lambda k: dists[k])
        mid = len(order) // 2
        median2 = dists[order[mid]]
        left_pts = [rest[k] for k in order if dists[k] <= median2]
        right_pts = [rest[k] for k in order if dists[k] > median2]
        node.radius2 = median2
        node.left = build(left_pts)
        node.right = build(right_pts)
        return node

    root = build(pts[:])

    def search(node, q, best_d2, best_idx):
        if node is None:
            return best_d2, best_idx
        d2 = dist2(node.vp, q)
        if d2 < best_d2:
            best_d2, best_idx = d2, node.vp[2]
        r2 = node.radius2
        d = math.sqrt(d2)
        r = math.sqrt(r2)
        best_d = math.sqrt(best_d2) if best_d2 < float('inf') else float('inf')
        if d < r:
            best_d2, best_idx = search(node.left, q, best_d2, best_idx)
            best_d = math.sqrt(best_d2) if best_d2 < float('inf') else float('inf')
            if r - d <= best_d:
                best_d2, best_idx = search(node.right, q, best_d2, best_idx)
        else:
            best_d2, best_idx = search(node.right, q, best_d2, best_idx)
            best_d = math.sqrt(best_d2) if best_d2 < float('inf') else float('inf')
            if d - r <= best_d:
                best_d2, best_idx = search(node.left, q, best_d2, best_idx)
        return best_d2, best_idx

    q_count = int(input_data[idx]); idx += 1
    out = []
    for _ in range(q_count):
        qx = int(input_data[idx]); idx += 1
        qy = int(input_data[idx]); idx += 1
        q = (qx, qy, -1)
        _, best_idx = search(root, q, float('inf'), -1)
        out.append(str(best_idx + 1))

    print('\n'.join(out))


solve()

Step-by-Step 解説

1k-d木との違い
k-d木は座標軸そのものに依存した分割を行う。VP-Treeは代表点からの距離だけで分割するため、座標軸という概念が存在しない距離空間にもそのまま適用できる汎用性が特徴。

2構築
各ノードで1点を代表点として選び、残りの点との距離を計算して中央値で内側/外側に2分割する。乱択で代表点を選ぶことで木の深さの期待値を$O(\log N)$にする。

3最近傍探索の枝刈り
クエリ点との距離$d$とノードの半径$r$を比較し近い側を先に探索するが、三角不等式により$|d-r|\le\text{best}$なら反対側も探索が必要と判定する。この枝刈りがVP-Treeの性能の核心。

4平方距離と実距離の使い分け
比較だけなら平方距離で十分だが、枝刈り条件は距離の差を扱うため$d^2-r^2\ne(d-r)^2$であり、実際の距離（sqrt後）で判定する必要がある。

5計算量
構築は$O(N\log N)$。1クエリあたりの探索は理想的には$O(\log N)$だが分布によって悪化することがある（最悪$O(N)$）。

よくあるミス

ミス	原因	正しい書き方
平方距離のまま枝刈り判定を行う	$d^2-r^2\ne(d-r)^2$であることを見落とす	枝刈り判定は実距離（sqrt後）で行う
代表点を常に先頭の点に固定する	偏った入力で木が偏る	乱択で代表点を選び期待計算量を保証する
反対側の探索条件を常に両方探索にする	枝刈りの意味を理解せず安全側に倒す	正しい距離判定で不要な探索を確実にスキップする
同点距離のタイブレークを忘れる	更新条件を`<`のみにする	距離が等しい場合のインデックス比較も条件に加える

次のステップ

発展: k近傍（k-NN）に拡張し、優先度付きキューで上位k個を保持しながら同様の枝刈りを行う
次回予告: Klee's Measure Problem（矩形群の合併面積・掃引線+セグメント木によるO(N log N)）

自己評価

完全理解おおむね理解要復習

Day 126-Q4 — Vantage-Point Tree（距離空間の最近傍探索）

問題