You may encounter using T-SNE algorithm. If your data is very high dimensional, T-SNE first reduces the number of dimensions by preserving their actual distances in original space. Then you can compute it with a less complexity fashion. Moreover, you may also try autoencoders to reduce the number of dimension. But, I first suggest t-SNE.

The following may help to put the average case linear-time algorithms (for the diameter of a finite set) in a clearer light, as well as contrast multi-dimensional and plane geometry problems.

In 1983 Megiddo gave a deterministic linear-time algorithm for the smallest enclosing circle (or sphere in higher dimensions).

In general position the enclosing circle will have two or three points on its boundary, and thus finding the two farthest apart can be done "on average" in constant time once the bounding circle is known. In higher dimensions the number of points in general position needed on the boundary of the sphere increases (D+1 points for dimension D), and indeed the cost of computing distance between a single pair of points rises linearly with dimension.

The subset of points lying on the bounding circle or sphere is also found in linear time. In the theoretical worst-case all points would lie on the bounding circle or sphere, but this at least is stricter than just having all points on the convex hull. If the points on the sphere are independently perturbed, say along radial lines, then general position is assured with probability 1, and an approximate diameter can be found from just D+1 points on the revised enclosing sphere. This randomized approximation has quadratic dependence on dimension but only linear complexity in number of points.

If the points lying on a bounding circle are "sorted" (cyclically, of course), finding the pair farthest apart can be done in linear time, relying upon the "unimodality" of the circle (meaning that distances from a fixed point rise monotonically until the antipode and then fall) to amortize the cost of computing distances. Unfortunately that sorting would introduce a step with O(n log n) time complexity, and this proves to be worst-case optimal for exact deterministic methods in the planar case.

In 2001 Ramos succeeded in showing an O(n log n) deterministic algorithm for three-dimensional sets, but the technique is so involved that an implementation may be impractical or slower than brute force all-pairs search up to very large datasets.

For higher dimensions many authors have considered randomized or approximate algorithms. See Piotr Indyk's thesis (2000) for approximate methods with only polynomial dependence on dimension for various proximity problems.

Between the Approximate Nearest Neighbor algorithms I think the most popular is Locality-Sensitive Hashing (LSH), which maps a set of points in a high-dimensional space into a set of bins.

.

Approximate Furthest Neighbor in High Dimensions

Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, and Matthew Skala

IT University of Copenhagen

Abstract.

Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider

approximate furthest neighbor (AFN) queries. We present a simple, fast, and highly practical data structure for answering AFN queries in high-dimensional Euclidean space. We build on the technique of Indyk (SODA 2003), storing random projections to provide sublinear query time for AFN. However, we introduce a different query algorithm, improving on Indyk’s approximation factor and reducing the running time by a logarithmic factor. We also present a variation based on a query-independent ordering of the database points; while this does not have the provable approximation factor of the query-dependent data structure, it offers significant improvement in time and space complexity. We give a theoretical analysis, and experimental results.

http://www.itu.dk/people/pagh/papers/approx-furthest-neighbor-SISAP15.pdf

.

I agree with Dr Son

The algorithm is a set of mathematical, logical and sequential steps necessary to solve a problem. The algorithm was named by the name Abu Jaafar Muhammad ibn Musa al-Khwarizmi, which he invented in the ninth century AD. The word in Latin and European languages ​​is «algorithm». Originally it meant only an algorithm for three structures: sequence, selection and repetition.

Sequence: The algorithm is a set of sequential instructions. These instructions may be either simple or of the following two types.

Check: Some problems can not be solved in a simple sequence of instructions. You may need to test some conditions and look at the result of the test. If the result is correct, follow a path containing sequential instructions. If wrong, follow a different course of instruction. This method is called decision making or selection.

Repetition: When solving some problems, the same sequence of steps must be repeated a number of times. This is called repetition.

It has proved that there is no need for additional structures. Using these three structures makes it easier to understand the algorithm and to discover and change the errors in it.

I agree with Peter, and appreciate his anger and compassion to science and ethics.

It is allowed to copy and paste answers at this platform as well as people cite and give credit to the original source.

I gently ask and wish for adding a citation for some of the above answers.

I understand that sometimes people unintentionally forget to do so, but there is always a way to edit an answer.

Still, I could not get a satisfying answer to my question yet.

I will be tempted to start by computing the miniball of the points. Probably this commonly used algorithm can be used as a basis to get the result directly.

For the miniball, you may have a look here: https://github.com/hbf/miniball or there: https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html

In the las link there is a link to this paper: https://people.inf.ethz.ch/gaertner/subdir/texts/own_work/esa99_final.pdf

Thank you Vincent for these references, but when I get the miniball, what to do to find the farthest pair of points?

As the number of points on the ball should be very small (excpet if your point distribution in on the sohere), using the naïve n^2 algorithm on them should not be a big cost.

Thanks Vincent, I will try it to compare my methods

Thank you guys, another research stems from RG discussions, see

Preprint Greedy Algorithms for Approximating the Diameter of Machine ...

You wrote an interesting paper. Did you tried to use A1 as a filter to get a subset of the points and then apply one of the A2-4 accurate methods? Does this enhance speed of the "alone" A2-4 methods?

Thanks Vincent, a hybrid the proposed methods might be better, but there is only one way to find out, Experiments!