Search in array with high dimensions having specific properties

Question

I have a 3D array in which values are monotonic. How to find all (x,y), |f(X,Y,Z) – v1| < t.

Answer 1

There are Omega(n^2) points whose coordinates sum to n - 1. Nothing is known a priori about how the values of these points compare to each other, so, in the worst case, all of them must be inspected. An upper bound that matches up to constant factors is provided by running the 2D algorithm in each constant-z slice.

Answer 2

For each value (eg. v1), execute the following steps:

1. Execute the 2D algorithm for the 4 cube faces tangent to the X axis (Y=0, Y=n-1, Z=0, Z=n-1). Index the resulting set of matching (X, Y, Z) cells by X coordinate for the next step.
2. Execute the 2D algorithm for all n slices along the X axis (X=0..n-1), using the result of step 1 to initialize the first boundary point for the 2D algorithm. If there are no matching cells for the given x coordinate, move on to the next slice in constant time.

Worst case complexity will be O(O(2D algorithm) * n).

For multiple values (v2, etc.) keep a cache of function evaluations, and re-execute the algorithm for each value. For 100^3, a dense array would suffice.

It might be useful to think of this as an isosurface extraction algorithm, though your monotonicity constraint makes it easier.