Open AccessA simple approximation algorithm for the diameter of a set of points in an Euclidean plane
Author(s) -
Jieying Hong,
Zhipeng Wang,
Ning Wei
Publication year - 2019
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0211201
Subject(s) - simple (philosophy) , algorithm , euclidean geometry , approximation algorithm , euclidean distance , set (abstract data type) , partition (number theory) , plane (geometry) , mathematics , simple algorithm , linear approximation , computer science , combinatorics , geometry , physics , philosophy , epistemology , nonlinear system , quantum mechanics , thermodynamics , programming language
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 + ε −1 log ε −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.