A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon
<|reference_start|>A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon: 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 $\varepsilon>0$, a set $\mathcal{C} \subset P$ of size $O(1/\varepsilon^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-\varepsilon$ times the geodesic distance to its further neighbor in $P$. Thus the set $\mathcal{C}$ can be used for answering $\varepsilon$-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}{\varepsilon} \left( n\log(1/\varepsilon) + (n+m)\log(n+m)\right) \right)$ time.<|reference_end|>
@article{de berg2024a,
    title={A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon},
    author={Mark de Berg, Leonidas Theocharous},
    journal={arXiv preprint arXiv:2403.04513},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04513},
    primaryClass={cs.CG}
}