title: What is an appropriate data structure for storing (samples of) a 2D function?
body: <p>I am looking for an efficient way of computing and storing the samples of a 2D function in my C++ program.</p>
  
  <p>In order to be specific, let me start with the problem in one dimension which is easy and then explain why I cannot generalize it into 2D:</p>
  
  <p><strong>The 1-D version is as follows:</strong> We compute the samples of a function z = f(x) in the following way. We read the data from the input and corresponding to each input we compute a value of x and z = g(x). Now, we have a table of (x,z = g(x)) pairs. If for any given x, there exist only one entry then we have f(x) = z. Otherwise, f(x) = z1 + z2 + ... (where z1, z2, ... are the corresponding z entries for the specific x).</p>
  
  <p>The above procedure can be implemented simply using a <code>std::multimap</code>. Namely at the first stage we just store the results in the map (with <code>x</code> as the key). Finally we can iterate through the map and if two adjacent elements are <em>close enough</em> we just merge them by adding their corresponding values. Assuming the complexity of computing x and z = g(x) is constant we can compute N samples in O(N log N) time complexity.</p>
  
  <p><strong>Now, I would like to generalize the algorithm into two dimensions</strong>. Namely we first compute (x,y,z=g(x,y)) pairs from the input and then set f(x,y) = z1 + z2 + ... (where for any fixed (x,y) pair, z1, z2, ... are corresponding z fields of the table entries starting with (x,y)). </p>
  
  <p>The previous solution cannot be generalized because of the simple reason that one cannot define an ordering on 2D plane (indeed we could use <code>std::multimap&lt;std::pair&lt;double,double&gt;,double&gt;</code> but then there is no meaningful comparison to see if a  key <code>x1,y1</code> precedes <code>x2,y2</code>). However, notice that there is notion of <em>closeness</em> on the 2D plane: given two points (x1,y1) and (x2,y2) we can precisely tell whether they should be merged in our output or not.</p>
  
  <p>Well, the very naive solution is to implement a  2D linked list (sorted in each dimension separately) where there is a better notation of adjacency. But this at least is very inefficient for insertion and (beside many other difficulties) the procedure would take O(M^2) time (where M = N * N is the number of samples on the 2D plane we want to compute)</p>
  
  <p>I wonder if there is a way (more precisely a data structure) who allows me to solve the problem more efficiently?</p>
  
  <p>I am really sorry for being very redundant and rather vague. </p>