Approximate Minimum Diameter

• Published in: arXiv.org 2017-03
• Main Authors: Ghodsi, Mohammad, Homapour, Hamid, Seddighin, Masoud
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Lower bounds; Mathematical analysis; Polynomials
• ISSN: 2331-8422

We study the minimum diameter problem for a set of inexact points. By inexact, we mean that the precise location of the points is not known. Instead, the location of each point is restricted to a contineus region (\(\impre\) model) or a finite set of points (\(\indec\) model). Given a set of inexact points in one of \(\impre\) or \(\indec\) models, we wish to provide a lower-bound on the diameter of the real points. In the first part of the paper, we focus on \(\indec\) model. We present an \(O(2^{\frac{1}{\epsilon^d}} \cdot \epsilon^{-2d} \cdot n^3 )\) time approximation algorithm of factor \((1+\epsilon)\) for finding minimum diameter of a set of points in \(d\) dimensions. This improves the previously proposed algorithms for this problem substantially. Next, we consider the problem in \(\impre\) model. In \(d\)-dimensional space, we propose a polynomial time \(\sqrt{d}\)-approximation algorithm. In addition, for \(d=2\), we define the notion of \(\alpha\)-separability and use our algorithm for \(\indec\) model to obtain \((1+\epsilon)\)-approximation algorithm for a set of \(\alpha\)-separable regions in time \(O(2^{\frac{1}{\epsilon^2}}\allowbreak . \frac{n^3}{\epsilon^{10} .\sin(\alpha/2)^3} )\).