<p><a href="https://i.stack.imgur.com/wexKD.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wexKD.png" alt="enter image description here"></a></p>

<p>Technically, if you are only looking for the points with maximum distance, you can build a polygon (convex hull) with the points, the maximum distance should be the ones in the border.</p>

<p>You can calculate convex hull in O(k.log(k)) </p>

<p><a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html" rel="nofollow noreferrer">https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html</a></p>

<p>After that, you need to just test points on the border.</p>

<p>This is the deterministic approach, you can apply heuristic, randomized search to do it faster but they are not guaranteed to provide the correct solution.</p>

<p>Here's a paper which discusses the topic with another algorithm: <a href="https://arxiv.org/ftp/arxiv/papers/1708/1708.02758.pdf" rel="nofollow noreferrer">https://arxiv.org/ftp/arxiv/papers/1708/1708.02758.pdf</a></p>
Maximum Distance of 2 sets of points with a 2-factor approximation
<p>given a set of n points , i take k points randomly. I need to compute in the most efficient way the <strong>maximum distance</strong> of the <strong>k</strong> points from the <strong>n</strong> points with a <strong>2-approx factor</strong> (exploiting in some way the triangular inequality).
A first idea I had was to use the Manhattan distance instead of the Euclidean Distance, but this does not reduce complexity as it is still <strong>O(n*k)</strong>.
What could be some ideas?</p>

<p>EDIT: what if i first compute the 2 farthest point in the k points and then calculate the distance of the 2 points from all the n points?</p>