Computing the diameter of a point set by a randomized incremental algorithm
1 year ago
Authors:
Nguyễn Khắc Quốc
Publication date:
01 / 06 / 2022
Name of Publishers:
Journal of Education Equipment
Abstract:
Approximation algorithms with linear complexity are widely used in big data processing. However, these algorithms cannot give complexity to the problem of computing the diameter of a point set. Using the partitioning technique, we construct a randomized incremental algorithm for the problem of finding the diameter of a set of points for points in any number of dimensions, and for any distance of all pairs of points in the metric space. In this study, we propose an algorithm to compute the diameters of n points with the expected running time of O(nlogn) for L2 in the metric space, and O(n) for L1 in the metric space.