My question is whether it is possible to identify the delaunay simplex the point $\mathbf{x}_{\textrm{query}}$ resides in without pre-calculating all the possible simplices by triangulation?
Can we query it efficiently but we haven't built the delaunay structure? (we have only points' locations)
My question here is somewhat different than others because the delaunay structure haven't been built.
My Target:
My task is to find those vertices of a simplex that contains a given query point $\mathbf{x}_{\textrm{query}}\in\mathbb{R}^d$.
The simplex we find should ideally be a delaunay simplex.
The solution should ideally avoid runing delaunay triangulation on all points to get all the simplices which waste storage.
Details:
I have $N$ $d$-dimensional point $\mathbf{P}\in\mathbb{R}^{N\times d}$ in total. A conventional approach is to perform delaunay triangulation, so that I can get all the possible simplex indices, e.g. $\mathbf{V}\in\mathbb{R}^{M\times (d+1)}$, where $M$ is the number of simplices, and each item of $\mathbf{V}$ is a point index to retrieve the corresponding row in $\mathbf{P}$. However, in my case, $N$ is quite large, and therefore $M$ becomes exceedingly large. Computing all the simplices could be infeasible.
We only care about the simplex containing the point, not all the other irrelevant simplices.
It would be nice to have the solution naturally support parallel implementation, and the complexity is as low as possible.
Generalized Case:
The problem can be generalized. We can introduce a function $f(\mathbf{x}_1,\ldots,\mathbf{x}_{d+1})$ whose return value is a bool indicating whether the simplex specified by its $d+1$ input points (i.e. $\mathbf{x}_1,\ldots,\mathbf{x}_{d+1}$) contains the point of interest $\mathbf{x}_{\textrm{query}}$.
Besides, such a function $f(\mathbf{x}_1,\ldots,\mathbf{x}_{d+1})$ could be any other function $f_{\textrm{any}}: (\mathbf{x}_1,\ldots,\mathbf{x}_{d+1}) \rightarrow \{\textrm{True}, \textrm{False}\}$ as long as it takes $d+1$ arguments as input, and outputs a bool.