Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!34g2000hsh.googlegroups.com!not-for-mail
From: Rune Allnor <allnor@tele.ntnu.no>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding minimum distance in a set of points
Date: Sat, 2 Aug 2008 03:05:21 -0700 (PDT)
Organization: http://groups.google.com
Lines: 29
Message-ID: <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>
References: <g6v8fd$ntc$1@fred.mathworks.com>
NNTP-Posting-Host: 212.17.141.54
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1217671522 3700 127.0.0.1 (2 Aug 2008 10:05:22 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 2 Aug 2008 10:05:22 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: 34g2000hsh.googlegroups.com; posting-host=212.17.141.54; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET 
Xref: news.mathworks.com comp.soft-sys.matlab:483264



On 1 Aug, 17:01, "Alan B" <mongui...@yahoo.com> wrote:
> Is there a good way in Matlab to find the minimum
> point-point distance in a set of points? I've come up with a
> few methods, and the best I've figured out so far is this:
...
> This seems to work pretty well, it beats for loops for N>20
> or so on my computer,

No, it doesn't. There are for-loops hidden inside the 'find'
and 'min' functions you use. You only see the diffrence between
two implementations of for loops.

> but it seems like there should be a
> better way. Also, I don't see a straightforward way to
> extend this to higher dimensions, which I would like to do.

This is a standard exercise in geometry. Check out the
1993 book by Preparata and Shamos to find an efficient
recipe.

> I basically wrote for loops to do it, and then tried to come
> up with an array of the indices that the for loops would
> generate, in order to vectorize the operation.

Forget about that. This is nothing more than a direct search
which requires O(N^2) time. The job can be done in O(NlogN)
time, but you need to use a completely different strategy.

Rune