Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding minimum distance in a set of points
Date: Sat, 2 Aug 2008 10:28:01 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 47
Message-ID: <g71crh$r25$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1217672881 27717 172.30.248.37 (2 Aug 2008 10:28:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 2 Aug 2008 10:28:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:483269



Rune Allnor <allnor@tele.ntnu.no> wrote in message
<bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>...
> 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.

The complexity of (well implemented) Delaunay algorithm in a
worse case is O(N^ceil(d/2)) and for well distributed point
set (more or less uniform) is O(N). N is number of points
and d is the dimension. So:

In 2D, Delaunay complexity is O(N) is any case.

In 3D, Delaunay complexity is O(N^2) in the worse case and
O(N) in average. Quite good no?

The post-search for min distance part is of course at
(d+1)*O(N) in complexity.

Bruno