Efficient Approximation Algorithm With Partition Technique For The Diameter Of A Set Of Points In 2D Plane
Zhipeng Wang, Jieying Hong, Wei Niu · Journal of Physics Conference Series · 2018
We apply the partition technique to build an efficient approximation algorithm to compute the diameter of a set of points in 2D Euclidean plane. The optimal time of our algorithm is O ( N + (1/ δ )log(1/ δ )), up to a (1 + δ ) factor, for 2-dimensional N -point set. The error bounds are proved strictly. Compared to the prior works, our algorithm is without complex data structure and easy to be implanted. The partition technique is general and may be applied in higher-dimensional space.