A Polynomial Coreset for Furthest Neighbor in Planar Metrics

A furthest neighbor data structure on a metric space $(V,\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t})$ and a set $P\subseteq V$ answers the following query: given $v\in V$, output $p\in P$ maximizing $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(v,p)$; in the approximate version, it is allowed to report any $p\in P$ with $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(v,p)\ge (1-\epsilon ){\max }_{p^{\mathrm{\prime }}\in P}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(v,p^{\mathrm{\prime }})$ for an accuracy parameter $\epsilon \in (0,1)$. A particular type of approximate furthest neighbor data structure is an $\epsilon$-coreset: a small subset $Q\subseteq P$ such that for every query $v\in V$ there is a feasible answer $p\in Q$. Our main result is that in planar metrics there always exists an $\epsilon$-coreset for furthest neighbors of size bounded polynomially in $(1\mathrm{/}\epsilon )$. This improves upon an exponential bound of Bourneuf and Pilipczuk [SODA’25] and resolves an open problem of de Berg and Theocharous [SoCG’24] for the case of polygons with holes. On the technical side, we develop a connection between $\epsilon$-coreset for furthest neighbors and an invariant of a metric space that we call an $\epsilon$-comatching index – a sibling of $\epsilon$-(semi-)ladder index, a.k.a, $\epsilon$-scatter dimension, as defined by Abbasi et al [FOCS’23]. While the $\epsilon$-(semi-)ladder index of planar metrics admits an exponential lower bound, we show that the $\epsilon$-comatching index of planar metrics is polynomial, all in $1\mathrm{/}\epsilon$. The exponential separation between $\epsilon$-(semi-)ladder and $\epsilon$-comatching is rather surprising, and the proof is the main technical contribution of our work.