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: Sun, 3 Aug 2008 12:04:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 74
Message-ID: <g746ri$7pt$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>  <6d4ad16f-e455-4759-9b03-1a5eb385cf30@d45g2000hsc.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 1217765042 7997 172.30.248.37 (3 Aug 2008 12:04:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 3 Aug 2008 12:04:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:483341



Rune Allnor <allnor@tele.ntnu.no> wrote in message
<6d4ad16f-e455-4759-9b03-1a5eb385cf30@d45g2000hsc.googlegroups.com>...

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

True, that would be indeed ideal, but I do not have time nor
enough expertise to read through all the papers I come
across and fully understand it. I do know that Fermat's
theorem have been proven, but I'm unable to read Wiles's
paper, and I will not hesitate to apply it in real life if
opportunity arises.

> 
> 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.

Read from these respective papers:

http://www.lis.inpg.fr/pages_perso/attali/Publications/lbcdtpps-sm02.ps

"It is well known that the complexity of Delaunay
triangulation of n point in R^d, i.e., the number of its
simplices can be O(ceil(d/2)) [Boissonnat, Yvinec,
Algorithmic Geometry, Cambridge Univ Press, UK, 1998]

http://cis.poly.edu/~aronov/papers/voronoi-lb.ps

In R^d, the problem has been explored with less success. The
worst-case complexity of Euclidean Voronoi diagram of points
is O(ceil(d/2)) and the same bounds have been proven for
Linfinity metric [Boissonnat, Shahir, Tagansky, Yvinec,
1998] [Edelsbrunner, 1987].

http://www.ii.uni.wroc.pl/~mbi/papers/2005-04-ewcg/average-voronoi-presentation.pdf

Worst case complexity O(ceil(d/2)) [Klee, 1980, Seidel 1987].

And FYI, I'm dealing with problem is real life since 10
years (However I cannot pretend I never make a mistake, but
I rarely make the same miskake twice). And if you wonder
where I'm graduate: The same university than Boissonnat who
has been cited above.

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

Thanks for the example, I appreciate it.

But may be I miss something: what you have shown is that the
lower bound complexity of an *INCREMENTAL* delaunay
tessalation is at best O(N*logN). Where does it shows that
*ALL* algorithms cannot beat it?

Just to make a metaphore: to show a sorting algorithm cannot
beat O(N*log(N)), one cannot take a quick sort algorithm as
case of study: Otherwise it would show a behavior of O(N^2)
in the worst case for sorting!

But dont' get me wrong: this does not mean that I reject
your conclusion of O(N.log(N)) for Delaunay in R^2. I'm
still not convinced yet from what has been shown.

So I'm modestly still persuaded by my previous bold
statement on the possible Delaunay complexity of O(N) on R^2.

Bruno