@NathanMerrill no you're right, I completely mixed up the two things: I am interested in the fewest number of evaluations of the function. The algorithm itself could be arbitrarily involved.
but lets say there is an O(n) algorithm, then we obviously cannot have O(n^2) evaluations:)
Another related question: Lets say we have some points in R^n how can we (efficiently) determine the most isolated point? (a point with the greatest distance to its closest neighbour)
Y'know, this is actually a really good point. An AI in control of unstoppable swarms of killer robots is just as scary when itself controlled by a human.
Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?
We define a most isolated point as by
$$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$$
(I used the $x=\arg\min$ notation even though it is not necessarily unique...
There are really four types of neighbors here: 1. The best friends (Nearest neighbor) 2. The loner (Most isolated point) 3. The social butterfly (Smallest distance to furthest point) 4. The enemies (Largest distance to furthest point)
Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?
We define a most isolated point as by
$$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$$
(I used the $x=\arg\min$ notation even though it is not necessarily unique...
