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 13:09:01 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 52
Message-ID: <g71m9d$5t4$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>  <e3533450-2671-4b94-839c-ce0d3c7b04de@m3g2000hsc.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 1217682541 6052 172.30.248.37 (2 Aug 2008 13:09:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 2 Aug 2008 13:09:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:483275



Rune Allnor <allnor@tele.ntnu.no> wrote in message
<e3533450-2671-4b94-839c-ce0d3c7b04de@m3g2000hsc.googlegroups.com>...

> 
> Have you actually read the paper or do you merely refer
> to what you think it says?
> 

No I haven't read it. But this result well known and I knew
it since I was lectured at university on the topic (I was
not in a geometry/computation department which is but 1/4 of
staffs of our math department is on this topic, I very good
friend of mine who works on this subject, actually on the
perturbation of triangulation by errors). If are interested
and wish to contact people on this topic for further detail,
just let me know.

Here is an experiment test with MATLAB on my PC, it shows a
quite good linearity:

N=10, time=0.147329
N=100, time=0.058632
N=1000, time=0.080535
N=10000, time=0.852366
N=100000, time=8.593533
N=1000000, time=89.974866

% Code
clear all
N=10.^(1:6); % 10 to a billion
time=zeros(size(N));
for k=1:length(N)
    % generate N points in 2D
    p=rand(N(k),2);
    
    % Delaunay way with array, even faster:
    tstart=tic;
    tri=delaunay(p(:,1),p(:,2));
    tri=tri(:,[1:end 1]);
    dP = diff(reshape(p(tri,:),[size(tri) size(p,2)]),1,2);
    d2 = sum(dP.^2,3);
    dmin = sqrt(min(d2(:)));
    time(k)=toc(tstart);
    fprintf('N=%d, time=%f\n', N(k), time(k));
end
% Plot time vs number of data point
loglog(N,time,'-o')
xlabel('Number of data')
ylabel('Time [s]')
grid on

% Bruno