Coresets for Farthest Point Problems in Hyperbolic Space

Abstract

We show how to construct in linear time coresets of constant size for farthest point problems in fixed-dimensional hyperbolic space. Our coresets provide both an arbitrarily small relative error and additive error $\epsilon$. More precisely, we are given a set $P$ of $n$ points in the hyperbolic space ${\mathbb{H}}^D$, where $D=O(1)$, and an error tolerance $\epsilon \in (0,1)$. Then we can construct in $O(n/{\epsilon }^D)$ time a subset $P_{\epsilon }\subset P$ of size $O(1/{\epsilon }^D)$ such that for any query point $q\in {\mathbb{H}}^D$, there is a point $p_{\epsilon }\in P_{\epsilon }$ that satisfies $d_H(q,p_{\epsilon })\ge (1-\epsilon )d_H(q,f_P(q))$ and $d_H(q,p_{\epsilon })\ge d_H(q,f_P(q))-\epsilon$, where $d_H$ denotes the hyperbolic metric and $f_P(q)$ is the point in $P$ that is farthest from $q$ according to this metric. This coreset allows us to answer approximate farthest-point queries in time $O(1/{\epsilon }^D)$ after $O(n/{\epsilon }^D)$ preprocessing time. It yields efficient approximation algorithms for the diameter, the center, and the maximum spanning tree problems in hyperbolic space.