TY - JOUR ID - 75162 TI - Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions JO - Journal of Algorithms and Computation JA - JAC LA - en SN - 2476-2776 AU - Imanparast, Mahdi AU - Hashemi, Seyed Naser AU - Mohades, Ali AD - Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Y1 - 2019 PY - 2019 VL - 51 IS - 2 SP - 47 EP - 61 KW - diameter KW - Point-set KW - Approximation algorithms KW - Higher dimensions DO - 10.22059/jac.2019.75162 N2 - 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. UR - https://jac.ut.ac.ir/article_75162.html L1 - https://jac.ut.ac.ir/article_75162_b7dd1282a7b33bb86cf9ad24b567cbc9.pdf ER -