Assume that I have a set of $N>3$ points $\{x_1,...,x_N\}$ in some $D$-dimensional space $\mathbb{R}^D$. It is my goal to identify the three points in this set which are the farthest away from each other, or more concretely, enclose the triangle with the largest area. You may assume that I have access to a $N$-by-$N$ matrix of pairwise distances.
My initial idea was to see which point has the largest distance to two other points, but this does not guarantee that those two points are far away from each other, and that some other combination of three points might not enclose a larger area. I could also brute-force the solution by systematically checking all combinations between points, but I wanted to know if there exists a more elegant solution.