Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity.
I can do some preprocessing on the given set of $N$ points. Up to around $O(N\log N)$ would be acceptable.
I want to repeat the lookup operation up to N times, so each individual operation would have to be around $O(\log N)$.
As Preprocessing, we can find the convex hull of the given points. It can be done in $O(N\log N)$. Suppose the convex hull is polygon $C_0$, $C_1$, $\cdots$, $C_{k-1}$, $C_k=C_0$. (The polygon could be degenerated.) Use binary search to find the triangle that contains the given point $P$, or the given point is outside of the polygon. This step takes $O(\log k) $ time.
While the approach above technically solves the problem stated in the title, I don't think it will produce good solutions in most cases, due to the fact that the vertices of the triangle will always be in the convex hull. This will produce quite big triangles. However, this could be the start of a solution, if there is a greedy improvement step afterwards.