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

Question

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.

• HEKTO: You can triangulate the point set, and then locate the query point in this triangulation. Keywords: Delaunay triangulation, point location in plane subdivision.

Answer 1

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.

Clarkson's algorithm has many desirable properties that are useful in practice. As a Las Vegas algorithm, it always gives some answer, albeit sub-optimal, if it is stopped early. While the running time is stochastic, the answer will always be correct, given enough time. (cf. Monte Carlo algorithms) The incremental nature of the algorithm makes it easy to handle robustness and input imprecision. Additionally, Clarkson's algorithm is easy to distribute over multiple computing agents, see e.g. our paper here.