Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Joost van der Laan, Frank Staals, Lorenzo Theunissen

We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain $P$ with $n$ ver…