computationally hard or not (algorithm question)

[Jörg Kaduk]

Hi all,
I am not an expert on anything either, but I would follow Adam in
saying Frank should look at geometric algorithms. 
I also think, depending on the problem it should be possible to avoid
to evaluate all point pair distances. I think, there should be 
algorithms, which determine hyperspaces from properties of the 
original set (convex would be nice). Using these hyperspaces
one should be able to reduce the amount of sorting significantly.
In 2d there are ways to cut the original set using hyperspaces (in this
case lines) and search only in the area determined by the cuts.
Unfortunately I do not know anything more about this, sorry.
Good luck,
Joerg

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

--
Jörg Kaduk                            Tel.: 1 650 325 1521 x 416
Carnegie Institution of Washington    FAX: 1 650 325 6857
Dept. of Plant Biology
260 Panama Street                     joerg at jasper.stanford.edu
Stanford, CA 94305-4150               http://Jasper.Stanford.EDU/joerg/