2017/03/31 by Mohammad Ghodsi, Ghodsi, Mohammad, Hamid Homapour +3
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1703.10976
arxiv created 2017/03/31 · arxiv updated 2017/04/03
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(1)/(εd) ⋅ ε-2d ⋅ n3 ) time approximation algorithm of factor (1+ε) 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 √(d)-approximation algorithm. In addition, for d=2, we define the notion of α-separability and use our algorithm for \indec model to obtain (1+ε)-approximation algorithm for a set of α-separable regions in time O(2(1)/(ε2)\allowbreak . \fracn3ε10 .sin(α/2)3 ).