Hello fellow MathExchangers,
I am wondering how can I proceed if I am given a set of 2D points as a list of $(x_i, y_i)$ and then another point, say $(x_0,y_0)$, and I would like to find the smallest shape/curve/region with grid points at the vertices that includes it.
It is obvious that the shape will be a triangle, unless of course $(x_0,y_0)$ is a point of the list, but other than brute forcing my way I can't figure out another approach. The number of 'grid' points I'd like to use are numerous, so brute force is not a viable solution.
Also, it is not implied anywhere that the 'grid' points are at regular intervals (hence the quotes), and anyway I'd like to find a way to solve this for any set of $(x_i, y_i)$, regular or not. The problem of course will be solved with a computer, so I don't have anything against complex methods/algorithms since it won't be solved manually.
I will have to repeat this calculation numerous times for a given set of $(x_i, y_i)$, so I don't mind if there is some way that requires much computational resources beforehand (maybe some preparational steps) but then makes it easy(fast) to find a solution, and I will code it myself so bonus points for approaches that can be parallelized (I could try GPU processing or something if necessary)
There are many ways to do a triangulation using $n$ given vertices. But there is one which has to be singled-out : "Delaunay triangulation" with many good properties. It is efficiently implemented (often using convex hull algorithm with O($n \log(n)$) complexity) in all scientific software (for example in Matlab). Delaunay triangulation, offers the possibility to efficiently retrieve the triangle which contains $(x_0,y_0)$. Moreover, it is known to be parallelizable.