Hector Tierno

Kacper Kluk, Hung Le, Wojciech Nadara et al.

A furthest neighbor data structure on a metric space $(V,\mathrm{dist})$ and a set $P \subseteq V$ answers the following query: given $v \in V$, output $p \in P$ maximizing $\mathrm{dist}(v,p)$; in the approximate version, it is allowed to report any $p \in P$ with $\mathrm{dist}(v,p) \geq (1-\varepsilon)\max_{p' \in P} \mathrm{dist}(v,p')$ for an accuracy parameter $\varepsilon \in (0,1)$. A particular type of approximate furthest neighbor data structure is an $\varepsilon$-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 $\varepsilon$-coreset for furthest neighbors of size bounded polynomially in $(1/\varepsilon)$. 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 $\varepsilon$-coreset for furthest neighbors and an invariant of a metric space that we call an $\varepsilon$-comatching index -- a sibling of $\varepsilon$-(semi-)ladder index, a.k.a, $\varepsilon$-scatter dimension, as defined by Abbasi et al [FOCS'23]. While the $\varepsilon$-(semi-)ladder index of planar metrics admits an exponential lower bound, we show that the $\varepsilon$-comatching index of planar metrics is polynomial, all in $1/\varepsilon$. The exponential separation between $\varepsilon$-(semi-)ladder and $\varepsilon$-comatching is rather surprising, and the proof is the main technical contribution of our work.

Hung Le, Hector Tierno, Shuang Yang

A quasi-metric $(T,δ_T)$ is an Okamura-Seymour quasimetric if there exists an edge-weighted planar embedded directed graph $G = (V,E,w)$ such that $T$ is a set of terminals on the outerface of $G$ and $δ_G(t,t') = δ_T(t,t')$ for every pair $(t,t')\in T\times T$. If $(T,δ_T)$ is an Okamura-Seymour quasimetric, then $G$ is a planar embedding of $(T,δ_T)$. In a recent pioneering work, Chen and Tan gave a polynomial-time algorithm to test if a given quasi-metric $(T,δ_T)$ is an Okamura-Seymour quasimetric. A key step in their proof is existential, which suffices for an efficient testing algorithm but does not imply an efficient embedding algorithm. Our paper closes this gap by giving an algorithmic implementation of their existential step via linear programming. As a result, we obtain the first polynomial-time algorithm for finding a planar embedding of any given Okamura-Seymour quasimetric $(T,δ_T)$. As an application, we show how to use our planar embedding of Okamura-Seymour quasimetrics to compute a $(1+ε)$-approximate single-source shortest path (SSSP) in planar directed graphs in the distributed CONGEST model in $\widetilde{O}(D)$ rounds for any fixed $ε\in (0,1)$, nearly matching a simple lower bound of $Ω(D)$ and resolving a fundamental problem in this area. The best-known algorithm for this problem has round complexity $\widetilde{O}(D^2)$.