グラフで最も近いエッジを見つけたい。次の例を検討してください。
図 1: 黄色:頂点、黒:エッジ、青:クエリ ポイント
一般情報: グラフには、約1,000 万の頂点と約1,500 万のエッジが含まれています。すべての頂点には座標があります。エッジは、隣接する 2 つの頂点によって定義されます。
最も簡単な解決策: クエリ ポイントからグラフ内の他のすべてのエッジまでの距離を単純に計算できますが、それは非常に遅くなります。
アイデアと難しさ: 私のアイデアは、空間インデックスを使用してクエリを高速化することでした。最も近い頂点を見つけるために、すでに kd-tree を実装しています。しかし、図 1 が示すように、最も近い頂点に付随するエッジは、必ずしもクエリ ポイントに最も近いとは限りません。より近いエッジ7-8ではなく、エッジ3-4を取得します。
質問: グラフで最も近いエッジを見つけるアルゴリズムはありますか?