Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!d45g2000hsc.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: Sun, 3 Aug 2008 03:18:23 -0700 (PDT)
Organization: http://groups.google.com
Lines: 133
Message-ID: <6d4ad16f-e455-4759-9b03-1a5eb385cf30@d45g2000hsc.googlegroups.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.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 1217758703 25506 127.0.0.1 (3 Aug 2008 10:18:23 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 3 Aug 2008 10:18:23 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: d45g2000hsc.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:483333



On 2 Aug, 21:02, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <e6b3bb92-4a70-4e6c-87b5-80c32a206...@j22g2000hsf.googlegroups.com>...
>
>
>
>
>
> > On 2 Aug, 18:21, "Bruno Luong"
> <b.lu...@fogale.findmycountry> wrote:
> > > Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> > > <8b35bb69-3422-4ee2-9ded-
>
> > > > So you don't know the *subject* but you know *people* who
> > > > know the subject?
>
> > > "knowing" is a not black and white thing IMHO, but yes
> > > geometry computation is not my major expertise and I don't
> > > deal with it daily - if that information is an important
> > > criteria for you Rune in the discussion.
>
> > It's not important to me in any other way than that it
> > explains why you come up with positively wrong information.
> > Knowing what you don't know is at least as important as
> > knowing what you do know. (Yes. That actually makes sense.)
>
> I see it's important for you despite you make the claim of
> the contrary. May be I'm wrong about O(N), at least I show a
> scientific paper with a results using may be a non valid
> assumption that escapes me. Fine.

Either that paper discusses something completeky different
than you think it does, or the claim put forward in that
aper is positively wrong.

> However what I expect from someone who really knows the
> topic is pointing to me what is the assumption used by the
> paper that is not true, thus why the claimed complexity is
> not right.

Nope. What you would expect is to read the paper yourelf
before you start talking about it as if you have.

> I have not read any of this in your post. You
> were merely giving examples two or three algorithms that do
> not have complexities go under O(N)log(N). This - of course
> you must be aware - does not disprove the claim of the paper.

I did point you to the obvious fact that a pathological
textbook example exists, which demonstrates that inserting
*one* point into a Delaunay tesselation which already
contains N points, is O(N) complexity.

> You wanted to prove you are the one who are working on the
> topic and I'm not, so my claim is false is your is right.
> You have not showed us why my claim is wrong beside telling
> it. That's what you were doing, and to be honest with you, I
> do not like this attitude at all.

That's too bad. I'm used to dealing with people who are able
and willing to read the basic literature before they make
bold statements. If that's an attitude which is problematic
to you, you might want to discuss your education and
preparation for real-life work with the Dean of whatever
university you went to, not with me.

As for the textbook example, it is utterly trivial and
is demonstrated by the matlab script below.

Define a sequence of points Pn = {p1,...,pn} where

pn = (a^(n-1),a^(2(n-1)))

where a is some real scalar 0 < a < 1. The sequence starts
at (1,1) and traces the parabola y=x^2 asymptotically
towards (0,0).

Define Dn as the n-point Delaunay tesselation of the set Pn.

Start with some tesselation Dn, n>2, add the next point pn+1
and compute the new tesselation Dn+1.

The key is to realize that none of the internal edges internal
to Dn (edges not on the convex hull of Dn) remain in the new
tesselation Dn+1. This means that with each point pn+1 added
to the tesselation, one needs to update *all* the n-3 or so
internal edges which already existed in the tesselation Dn.

This is O(N^2) behaviour as clear as it comes.

In the script below you can see this very clearly, as the
previous tesselation Dn-1 is plotted in red under Dn which
is plotted in blue.

Rune

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
PlotRows = 3;
PlotCols = 3;
NPlots = PlotCols*PlotRows;

a=0.7;

P=reshape(0:NPlots+1,NPlots+2,1)*[1,2];
P = a.^P;

clf
for n=1:NPlots
   pp=P(1:n+2,:);
   Dn=delaunay(pp(:,1),pp(:,2));
   subplot(PlotCols,PlotRows,n)
   dn=trimesh(Dn,pp(:,1),pp(:,2));
   hold on
   for m=1:length(dn)
       set(dn(m),'color','b');
   end
   plot(pp(:,1),pp(:,2),'.b')
   axis([-0.05,1.05,-0.05,1.05])
   set(gca,'xtick',[],'ytick',[])
   ts=['D_{',num2str(n+2),'}'];
   title(ts,'interpreter','tex')

   if n<NPlots
     subplot(PlotCols,PlotRows,n+1)
     dn=trimesh(Dn,pp(:,1),pp(:,2));
     hold on
     for m=1:length(dn)
       set(dn(m),'color','r');
     end
   end
end