Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions

	Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions
Journal of Algorithms and Computation
مقاله 5، دوره 51، شماره 2، اسفند 2019، صفحه 47-61 اصل مقاله (405.45 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2019.75162
نویسندگان
Mahdi Imanparast^* ؛ Seyed Naser Hashemi؛ Ali Mohades
Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
چکیده
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.
کلیدواژه‌ها
Diameter؛ Point-set؛ Approximation algorithms؛ Higher dimensions

آمار تعداد مشاهده مقاله: 489 تعداد دریافت فایل اصل مقاله: 252

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب