Selecting vertices in a convex polygon Given $n$ vertices of a  convex polygon in $\mathbb{R}^2$, selecting two points that are furthest apart is done by finding the diameter in a convex polygon. But how can one select three vertices such that the minimum distance between them is maximized?
Yes, it can be done by iterating over all possible combinations of three vertices which will take $O(n^3)$ time. Is it possible to do it in less time? —maybe in $O(n^2\log n)$ time.
EDIT: I believe that finding k vertices such that minimum distance is maximized is a difficult problem.
 A: Solution in time $O(n^2\log{n})$ is easy: use binary search over the answer (there are at most $n^2$ possible answers) and for a given answer the question boils down to finding a triangle in a graph on $n$ vertices (with edges between any two points at distance at least $d$ from each other). For a general graph this takes time $O(n^\omega)$ but here it is much easier: Fix one vertex, among other vertices select those at distance at least $d$ from it and check is the diameter of this set is at least $d$. We can compute diameter in time $O(n)$ since vertices are already in a convex position. So total time is $\log{n}$ for the binary search, $n$ for selecting one vertex and $n$ for computing diameter of the set of points at distance at least $d$ from it. This gives total complexity $O(n^2\log{n})$.
A: Partial answer: Sadhu et al. (2020) report an $O(n^2)$ algorithm for a closely related problem: Finding a triangle inside a convex polygon so as to maximize the shortest side of the triangle.
Note than unlike the present problem, Sadhu et al. do not require all three vertices of the triangle to be vertices of the original polygon. However, they do prove that at least one of the vertices of such a triangle will coincide with a vertex of the polygon.
I have not checked their algorithm, but here is a verbatim quote of their main theorem. ($\delta$ refers to the shortest side of the triangle.)
Theorem 4. Given a convex polygon $P$, the triangle $\Delta$ inside $P$ with longest $\delta(\Delta)$ can be obtained in $O(n^2)$ time.
Sadhu, Sanjib; Roy, Sasanka; Nandi, Soumen; Nandy, Subhas C.; Roy, Suchismita, Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon, Int. J. Found. Comput. Sci. 31, No. 4, 421-443 (2020). ZBL1462.68209.
A preliminary version of their work appeared in ICCSA 2017. It may be easier to access, but there they report only an $O(n^2 \log n)$ algorithm.

*

*https://link.springer.com/chapter/10.1007%2F978-3-319-62395-5_35
