OT: computationally hard or not (algorithm question)

[Frank Joerdens]

I've been lurking on this this list for a few months cuz I think
beowulfs are cool - but so far I've had neither the money nor any use
for one. Now I have a problem which might fall into the general vicinity
of beowulfery (but then again, it might not). You might have a pointer
to the relevant resources (Yes! I am willing and able to RTFM!):

Consider an n-dimensional array containing something on the order of
10^4 (i.e. thens of thousands) elements, where each number may assume an
integer value between 1-12. For the sake of the argument (it's easier to
visualize; actually, n would be something on the order of a dozen),
assume that n is 3, so you're basically looking at a box-shaped cloud of
dots in 3-D space, where each dot's position is defined by its
three-dimensional carthesian co-ordinates which are stored in the array.

Now, take any one of those dots, search for the 10 (some figure on this
order of magnitude) dots which are closest to it, and order those by
proximity to the origin of the search.  This sounds pretty hard,
computationally. Not for 3 Dimensions, since there the number of
possible positions is only 12^3 = 1728, but for 12, its 12^12 =
8916100448256. I guess you'd have to find some efficient shortest-pair
algorithm that works for n dimensions (my algorithm book only has one
that works for 2), find the shortest pair, remove it from the array,
then find the next value etc..

Does anyone have an idea, or a pointer to some reading matter about it,
as to how computationally expensive that would be? Any guess as to what
kind of hardware you'd have to throw at it (I could settle for less
dimensions if it turns out that I can't afford the hardware) when I want
the result set within a couple of seconds at the _very_ most?

Does anyone have a link to an article about the best algorithm for this
kind of problem?

Many thanks in advance,
Frank