A simple approximation algorithm for the diameter of a set of points in an Euclidean plane.
Where this comes from
- Record sourced from PubMed, PMID 30735522.
- Also identified by DOI 10.1371/journal.pone.0211201 and PMC identifier 6368283.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
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.
Medical subject headings
- Algorithms