# Filling the plane with a sequence

I am not sure if this is the right stack to ask this question, but since there is a definite fractal dimension to it, I thought I'd give it a go.

The problem I am facing is one of calculating an expensive function $f(x,y)$ in a finite 2D domain $D$. I perform the evaluation of $f$ at each point in $(x,y)$ independently from all other $(x,y)$ points.

The dumb way to parallelise the process of "scanning" $f$ over $D$ was to define a fixed rectangular grid of points covering $D$. By creating a trivial correspondence between integers and the position in the grid, I can assign each parallel task a range of integers to work with. I.e., each integer maps to only one point in $D$.

The solution above has a huge drawback: I cannot have a quick preview of what $f(x,y)$ looks like. The problem is akin to the one solved by progressive image encoding: I want to be able to refine the picture of $f(x,y)$ as I add more points.

The way I am framing the problem as is: how to map integers to a series of $(x,y)$ points which never repeat while becoming denser on an average way as the integer value increases.

This made me go straight to space-filling curves or trees: I could triangulate $D$ and in each triangle iterate to the desired scale. In this scheme, the number of points evaluated at iteration $n$ is $4\times(4-1)^{n-1}$. For instance, at iteration 3 there are 36 new points (which is different from the points in this example), and I would easily find myself "filling in" a certain corner of the triangle before others, resulting in a rather "non-progressive" way of filling in the triangle.

So, even if this would be a way to iteratively improve the density, in each iteration the overall sampling density would not be balanced (uniform) across $D$.

Any ideas on how to make the sampling in each iteration more uniform are very welcome.

• It sounds like you're really trying to count out the pixels in a rectangular region in such a fashion that after each round of pixels added (where a round is of a fixed size) the filled-in pixels are fairly uniformly distributed, right? Commented Aug 27, 2013 at 20:34
• I suspect the key general idea is to "collate" the breadth-first ordering so that you do one bit of work in each area at a time. Commented Aug 27, 2013 at 20:40
• Regarding uniformity, yes, it would great if every new point would keep the density uniform; sticking to the triangular space-filling tree example, that would imply at a given (large) iteration number some (fanciful) way of "spiraling" around the zones close to each of the triangle vertices and not just cover all points close to each of them in order. As for the breadth-first, the problem is still the same: if I split $D$ into $n$ disjoint pieces, I would still want to submit for processing in an order that preserves the uniformity criterium. This is why I put in the recursive tag. Commented Aug 28, 2013 at 9:27