We study the problem of computing the diameter of a set of $n$ points in $d$-dimensional Euclidean space for a fixed dimension $d$, and propose a new $(1+\varepsilon)$-approximation algorithm with $O(n+ 1/\varepsilon^{d-1})$ time and $O(n)$ space, where $0 < \varepsilon\leqslant 1$. We also show that the proposed algorithm can be modified to a $(1+O(\varepsilon))$-approximation algorithm with $O(n+ 1/\varepsilon^{\frac{2d}{3}-\frac{1}{2}})$ running time. Our proposed algorithms are different with the previous algorithms in terms of computational technique and data structures. These results provide some improvements in comparison with existing algorithms in terms of simplicity and data structure.
Imanparast,M , Hashemi,S N and Mohades,A . (2019). Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions. Journal of Algorithms and Computation, 51(2), 47-61. doi: 10.22059/jac.2019.75162
MLA
Imanparast,M , , Hashemi,S N , and Mohades,A . "Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions", Journal of Algorithms and Computation, 51, 2, 2019, 47-61. doi: 10.22059/jac.2019.75162
HARVARD
Imanparast M, Hashemi S N, Mohades A. (2019). 'Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions', Journal of Algorithms and Computation, 51(2), pp. 47-61. doi: 10.22059/jac.2019.75162
CHICAGO
M Imanparast, S N Hashemi and A Mohades, "Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions," Journal of Algorithms and Computation, 51 2 (2019): 47-61, doi: 10.22059/jac.2019.75162
VANCOUVER
Imanparast M, Hashemi S N, Mohades A. Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions. J. Algo. Comp.. 2019;51(2):47-61. doi: 10.22059/jac.2019.75162
