Find the three closest surrounding neighbors from a data

Question

I have a data of coordinates $x$ and $y$ where we know the range of both variables, e.g. $(x,y)\in[0,1]^2$. So for a given any random point $\theta_0=(x_0~~y_0)^T$ in the range of $x$ and $y$ I would like to find the closest 3 points to $\theta_0$ from my data that form a triangle where $\theta_0$ is included in that triangle (could be either on the edge or the center). So what are the coordinates of those three points from my data.

Answer 1

I think one should compute all the euclidean distances between $\theta_0$ and all the other points from the data then sort them. The first 3 points that don't form a straight line is the triangle that we are looking for. We can first find the slopes of the segments joining any two pairs of the 3 points. If they are different then it's a triangle. The last thing to do is to check also whether $\theta_0$ lies inside the triangle defined by the 3 points.