A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

Let P be a simple polygon with m vertices and let P be a set of n points inside P. We prove that there exists, for any ε>0, a set C ⊂ P of size O(1/ε²) such that the following holds: for any query point q inside the polygon P, the geodesic distance from q to its furthest neighbor in C is at least 1-ε times the geodesic distance to its further neighbor in P. Thus the set C can be used for answering ε-approximate furthest-neighbor queries with a data structure whose storage requirement is independent of the size of P. The coreset can be constructed in O(1/ε ( nlog(1/ε) + (n+m)log(n+m)) ) time.