Fast Approximation and Randomized Algorithms for Diameter

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'\), we have...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2014-10
Main Authors: Alipour, Sharareh, Kalantari, Bahman, Homapour, Hamid
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Randomization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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'\), we have \({\rm diam}(S) \leq \sqrt{3} d(q,q')\). Furthermore, iteratively replacing \(p\) with an appropriately selected point on the line segment \(pq\), in at most \(t \leq n\) additional iterations, the constant bound factor is improved to \(c_*=\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}\).
ISSN:2331-8422