# An efficient way of finding the closest point of a sampled function to another point

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$$.

• Is there any relation between the $n^2$ points or are they "random" ?
– user16034
Sep 25 at 20:05
• @user16034 In fact, they are coordinates in an image, and f(x) goes across the image (from left to right). Sep 29 at 19:11

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.

• Interestingly a kd-tree could reduce the number of iterations spent on finding the minimum, but not sufficiently to compensate for the higher overhead at each iteration, making it slower. Sep 29 at 19:12
• Without knowing the data and the implementation its hard to say. Maybe $n$ is too small for kd-tree to be useful? Are You fitting the function to the points? In that case You could build a kd-tree of the points instead of for the function values. Sep 30 at 0:38
• Here, n is in the range 1024 to 4096. Sep 30 at 9:40
• That feels relatively small for kd-trees to me. Building the tree may be more expensive than the savings in query time. Sep 30 at 9:43
• Actually building the tree is quick enough. However, individual lookups take way longer than they should. Oct 1 at 17:36