# find 3 points among some given 2D points such that the triangle includes another given point

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.

• You can triangulate the point set, and then locate the query point in this triangulation. Keywords: Delaunay triangulation, point location in plane subdivision. Jan 21 at 15:20

You can use Clarkson's algorithm to find the smallest (non-degenerate) enclosing triangle in $$O(d\log^2 n)$$ expected time, where $$d$$ is the dimension of your input. So, for constant dimensions, it takes $$O(\log^2 n)$$ expected time. The algorithms is applicable, because the smallest triangle problem is an LP-type problem.