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

Abstract

Let $\mathcal{P}$ be a simple polygon with $m$ vertices and let $P$ be a set of $n$ points inside $\mathcal{P}$. We prove that there exists, for any $\epsilon >0$, a set $\mathcal{C}\subset P$ of size $O(1/{\epsilon }^2)$ such that the following holds: for any query point $q$ inside the polygon $\mathcal{P}$, the geodesic distance from $q$ to its furthest neighbor in $\mathcal{C}$ is at least $1-\epsilon$ times the geodesic distance to its further neighbor in $P$. Thus the set $\mathcal{C}$ can be used for answering $\epsilon$-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\left(\frac{1}{\epsilon }\left(n\log (1/\epsilon )+(n+m)\log (n+m)\right)\right)$ time.

arXiv commentTo appear in SoCG 2024