ツリー検索アルゴリズム、特にクワッド ツリーと r ツリーに関して、最近傍を見つける際にエッジ エラーをどのように説明しますか。言葉で説明するのが苦手なので、絵を描いてみました。
画像の場合、最も近い隣人を見つけるための入力座標は緑で、「見つかった」最も近い隣人は赤です。実際の最近傍は青色です。
このクワッド ツリーでは、青色の右下の象限がその 1 つの赤い点のみで検索されますが、実際には、入力座標 (緑) はエッジに非常に近く、実際には青色の点により近くなっています。
座標が 1 つの四角形内にあるがエッジに非常に近い場合、R ツリーと同様に、次のように別の四角形のポイントに近くなります。ここで、白い点は座標が指定されています。
完全に赤いボックス内にありますが、マゼンタ ボックス内のポイントに近くなっています。
If you would bother to read the R-tree publication...
It uses a minimum distance, of the query point to a neighboring page.
If mindist(query, rectangle) <= dist(query, known neighbor) then the search needs to continue in the other rectangle, because there could be a better neighbor there.
It's actually quite straightforward, and should be explained in any book on R-trees and similar indexes.