Fast Approximation and Randomized Algorithms for Diameter

Abstract

We consider approximation of diameter of a set $S$ of $n$ points in dimension $m$. E$\tilde{g}$ecio$\tilde{g}$lu and Kalantari \cite{kal} have shown that given any $p\in S$, by computing its farthest in $S$, say $q$, and in turn the farthest point of $q$, say $q^{\prime }$, we have $\mathrm{diam}(S)\le \sqrt{3}d(q,q^{\prime })$. Furthermore, iteratively replacing $p$ with an appropriately selected point on the line segment $pq$, in at most $t\le n$ additional iterations, the constant bound factor is improved to $c_{\ast }=\sqrt{5-2\sqrt{3}}\approx 1.24$. Here we prove when $m=2$, $t=1$. This suggests in practice a few iterations may produce good solutions in any dimension. Here we also propose a randomized version and present large scale computational results with these algorithm for arbitrary $m$. The algorithms outperform many existing algorithms. On sets of data as large as $1,000,000$ points, the proposed algorithms compute solutions to within an absolute error of $10^{-4}$.

13 pages, 6 figures, 3 tables