Let S be a set of points in $\mathbb{R}^2$. Given a point $p \in \mathbb{R}^2$, how can we find a set of $3$ points $(a,b,c)$ in $S$ so that the triangle $abc$ contains $p$ and the circumscribed circle of $abc$ contains no other points of $S$?
One way I thought of doing this is to calculate the Delaunay triangulation of $S$, and then check whether each triangle contains $p$. This seems inefficient, as one might end up checking every triangle before getting to the one that actually contains $p$. Is there a more efficient way of doing this?
Suppose that the smallest distance between $p$ and a point in $S$ is $k$. Consider then the circle around $p$ with radius $k'<k$. Thus, we guarantee that no other point of $S$ lies inside the circle. You just need to select three points on the circle such that the triangle they form is acute (in order the circumcenter to be inside the triangle). This can be done via the triangular inequality, i.e., if wlog $AB$ is the longest side, then you just need to check that $AB^2<BC^2+CA^2.$