Hi!

Not sure whether I get your questions right. (It’s too late and I should definitely go to bed. )
I think you could precompute some sort of priority queue, by doing a breadth-first search. Starting from the center you use the breadth-first search to add the indices of the nodes to the priority queue that have a distance to the center smaller than radius r. The priority would be the distance to the center. You could keep a hash map telling you at which index a new radius in the priority queue begins. Then you iteratively increase the search radius and continue your breadth-first search until nothing else was found for the respective radius.

For your range queries you could simply traverse your priority queue until you reach the maximum index stored for your search radius in the hash-map. With this hash map you could also do range queries in a ring around the center (only for discrete search radii).
If you store the nodes relative to the center you can move the pattern like a filter around.

Is that what you’ve been looking for?
The data structure is not perfect for iterations in terms of performance, since the order of the nodes in the priority queue is in no way aligned to the layout of the memory.
Perhaps a better option would be to just store for each radius a list of start indices per row and a length of the row. Cache coherence would be much better, if you iterate this way. (You could find the indices by a breadth-first search, too, which means you can build up the data structure for an arbitrary number of radii in O(n)).

Cheers!

What I want is an algorithm which can pregenerate adjacency sets for the common radii.[/quote]

What do you mean by common radii? Or do you mean all radii?

Since you're pregenerating this just once, why not just bruteforce it? You don't really care if it runs for a few minutes while you go get a drink, since the users of your games will never experience this.

Brute-force solution (roughly accurate):

1. For each cell in the given color matrix, (keep incrementing RADIUS in desired range)
|-- a. iterate from (cell_x - RADIUS, cell_y - RADIUS) to (cell_x + RADIUS, cell_y + RADIUS):
|----- i. check if the given coordinate satisfies the circle equation, i.e. (cell_x - point_x)^2 + (cell_y - point_y)^2 <= RADIUS^2. [1]
|----- ii. If yes, add the coordinate (point_x, point_y) to a temporary list.
|-- b. Add the list as the value in a temporary hash, with the key being the RADIUS value. This hash then becomes the value to a master hash with the key (cell_x + "," + cell_y).


You can use priority lists to keep the cell coordinates sorted by color if you want.

I'd just say keep this simple, since it's easy to get carried away for precomputing things and write unnecessarily elaborate solutions.

[1] http://en.wikipedia.org/wiki/Circle#Equations