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 (n (1/) + (n+m) (n+m) ) ) time.