computationally hard or not (algorithm question)

[Adam Getchell]

Hi Frank,

I'm not an expert or anything, but I happen to have "Introduction to
Algorithms" by Thomas Cormen, Charles Leiserson, and Ronald Rivest ("CLR"
for short) and Chapter 35, Computational Geometry, might have what you're
looking for.

The closest points algorithm they used is based on divide and conquer, and
runs in O(nlgn) time. It's a 2-D algorithm, but I don't *think* generalizing
to n-dimensions will change things since the first step is to do a sort on
the X and Y coordinates which is O(nlgn) time per dimension, but done
serially so running time shouldn't be affected. (Well, actually, you store
your points in an appropriate data structure and keep a table of pointers
for each dimension and sort those ....)

However, if you want more immediate satisfaction the basic algorithm is also
described here:

http://www.cs.cornell.edu/cs409-sp99/Lectures/Lecture%2010/sld002.htm

The divide part shouldn't be hard, since the line will still divide your
region in to (XL, XR) (YL,YR) (ZL,ZR) ... for each dimension. I'm not
certain how constraining your "box" will be; for 2-D you can reduce it to
checking 7 other neighbors, but generalized for a hypercube of n dimensions
the points might be a bit larger. You say 12 dimensions? CLR mentions using
L-distance (or Manhattan distance) instead of Euclidean distance ... perhaps
that may make it more tractable.

A practicing computer scientist probably has a much better idea than my
naive ramblings ....

Hope that helps,

--Adam
acgetchell at ucdavis.edu

----- Original Message -----
From: "Frank Joerdens" <frank at joerdens.de>
To: <beowulf at beowulf.org>
Cc: <ttt at archi-me-des.de>; <adam at archi-me-des.de>; <deadmovintarget at web.de>
Sent: Friday, March 23, 2001 6:48 AM
Subject: OT: computationally hard or not (algorithm question)


> 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
>
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit
http://www.beowulf.org/mailman/listinfo/beowulf
>