Is there a proximity map algorithm or data structure?

Question

A problem I keep running into when writing code that draws images of scientific data is the following:

Given some floating point data, fit those data into slots (1-dimensional case) or a grid (2-dimensional case) such that each datum is in the slot or grid entry whose value is closest to the datum's value.

It is not the case that the slot/grid values are evenly spaced.

For example, put the following data into the following slots:

data: 0.1, 0.6, 4.23, 5.1, 7.0

slots: 0.0, 0.4, 0.6, 1.2, 5.0, 10.0

In practice, there are far more data than there are slots. So it would be beneficial to have a data structure that kept the slots in cache together.

What would be nice is something like a tree or a hash table, where you ask the tree for the value that corresponds to a key, but with sloppy comparisons that yield the closest match.

Does such a beast exist?

(Right now, I just have loops that do lots of comparisons. It seems like I could at least do better by using a binary search through the slots, though...)

Answer 1

Take a look at k-d trees.

Answer 2

For the 2D case, I would recommend Voronoi diagrams which are well covered by most computational geometry texts