Note: I'm very much from a programming background, not a mathematics background. This will become obvious very quickly.
Assume I have a bounded n-dimensional space - for example here I'll use n=2. In that space, I have a set of pre-defined points. (As it happens, I'm doing something questionable with genetic algorithms for finding minima in non-mathematically-solvable equations, but that's not directly relevant).
Next, I have defined a new point within that 2D space. I want to know which three (n+1) points form the smallest (or possibly nearest?) triangle that contains that point. Illustration here:
Now, as that illustration shows, I'm not entirely sure what I'm doing, in that I've failed to adequately describe the criteria by which the candidate triangles are judged - points 10, 5, and 8 would enclose the point within a triangle of smaller area, for example. This is because those specifics are somewhat flexible. What I really care about is:
- Computational efficiency: I could potentially end up scaling this algorithm up to thousands of points in a hundred dimensions. As such, I need a solution that's better than exhaustively testing every potential convex hull against a specific equation, and ideally one with a decent big-O notation. Presumably I'm going to need a more intelligent structure that a big unordered list to do this.
- If I had a preferred criteria, it's proximity of the hull vertices to the test point. However, if it's easier to build an algorithm which judges by area/volume or something else, I can live with that.
- I need to be able to handle edge-cases, where the test-point is, for example, on the edge between two vertices.
Where do I even start with this? Some cursory googling suggests Voronoi diagrams might be a step in the right direction, is that correct? What are the right tools for this job? Any help would be greatly appreciated.