I have a function $f(x)$, has been sampled into a sequence $$ y_0, y_1, ..., y_{n - 1} $$ at points $x_k = k \Delta x$. $f(x)$ is neither smooth or monotone.
Under this assumption, what is the fastest way of finding $$ \min_{k=0}^{n - 1}|P - (x_k, y_k)| $$ where $P$ is an arbitrary point?
I could do a linear search, but I need to compute the minimum distance for $n^2$ different points which makes the overall algorithm $n^3$.
You can construct a Voronoi diagram for your points, and then use a point location algorithm. Because you need quadratic work regardless you don't even need an efficient algorithm for the Voronoi diagram.
If You sample the function once beforehand, the problem breaks down to a simple Nearest Neighbor Search. There are many different data structures and algorithms for solving the nearest neighbor problem.
As long as $x_k$ and $y_k$ are fairly low-dimensional, one popular solution is the kd-tree which can be build in $\mathcal{O}(n \log{n})$ for your $n$ sample points. Querying the closest sample points to the $n²$ search points usually takes $\mathcal{O}(n^2\log{n})$.
Kd-tree libraries are available in most programming languages, e.g. for NumPy, there is scipy.spatial.KDTree. Kd-trees are a fast general purpose solution but likely not the fastest specific solution.
