TY - JOUR
T1 - A simple approximation algorithm for the diameter of a set of points in an Euclidean plane
AU - Hong, Jieying
AU - Wang, Zhipeng
AU - Niu, Wei
N1 - Publisher Copyright:
© 2019 Hong et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
PY - 2019/2
Y1 - 2019/2
N2 - Approximation algorithms with linear complexities are required in the treatments of big data, however, present algorithms cannot output the diameter of a set of points with arbitrary accuracy and near-linear complexity. By introducing the partition technique, we introduce a very simple approximation algorithm with arbitrary accuracy ϵ and a complexity of O(N+ ϵ-1log ϵ-1) for the cases that all points are located in an Euclidean plane. The error bounds are proved strictly, and are verified by numerical tests. This complexity is better than existing algorithms, and the present algorithm is also very simple to be implemented in applications.
AB - Approximation algorithms with linear complexities are required in the treatments of big data, however, present algorithms cannot output the diameter of a set of points with arbitrary accuracy and near-linear complexity. By introducing the partition technique, we introduce a very simple approximation algorithm with arbitrary accuracy ϵ and a complexity of O(N+ ϵ-1log ϵ-1) for the cases that all points are located in an Euclidean plane. The error bounds are proved strictly, and are verified by numerical tests. This complexity is better than existing algorithms, and the present algorithm is also very simple to be implemented in applications.
UR - https://www.scopus.com/pages/publications/85061257814
U2 - 10.1371/journal.pone.0211201
DO - 10.1371/journal.pone.0211201
M3 - 文章
C2 - 30735522
AN - SCOPUS:85061257814
SN - 1932-6203
VL - 14
JO - PLOS ONE
JF - PLOS ONE
IS - 2
M1 - e0211201
ER -